프로그래머스 - 가장 큰 수

카테고리: 정렬

레벨: 2

언어: Java

 

문제

---

 

입출력 예시

---

 

풀이

---

public String solution(int[] numbers) {
    String[] str = new String[numbers.length];
    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < str.length; i++) {
        str[i] = String.valueOf(numbers[i]);
    }

    Arrays.sort(str, ((o1, o2) -> (o2 + o1).compareTo(o1 + o2)));

    if (str[0].equals("0")) {
        return "0";
    }

    for (int i = 0; i < str.length; i++) {
        sb.append(str[i]);
    }

    return sb.toString();
}

처음에 문제를 접근했을 때 생각보다 풀기 쉬운 문제일 거라 생각했었다. 하지만 풀 다 보니 정렬하는 부분에서 막혔는데 다른 사람들의 코드를 참고해 보니 많은 사람들이 람다식을 사용해서 푼 것을 보고 람다식을 사용해 봤다.

먼저 코드를 설명해 보면 매개변수로 받은 numbers를 String 배열에 저장해야 되는데 이때 String 클래스의 valueOf 메서드를 사용하여 numbers 배열에 해당하는 i번째 정수 값을 문자열로 바꿔서 저장하였다.

그다음 이 코드의 핵심인 정렬을 Arrays 클래스의 sort 메서드를 사용하였는데 Comparator 인터페이스를 구현할 수 있어 람다식을 사용하여 정렬을 진행하였다.

람다식과 Comparator, Comparable에 대해서 지식이 부족하여 다른 사람들의 코드를 참고하여 구현했는데 추가적인 공부가 필요해 보였다.

정렬이 끝나면 해당 배열의 0번째 인덱스에 위치한 값을 확인하는데 만약 0이라면 해당 배열에서 만들 수 있는 가장 큰 수는 0이라고 판단할 수 있다.

마지막으로 StringBuilder를 사용하여 데이터를 입력받아 출력하는 코드를 구현했다. 굳이 StringBuilder를 사용한 이유는 String 클래스로 처리하는 것보다 StringBuilder를 통해서 처리하는 것이 효율적인 면에서 더 좋기 때문에 사용하였다.

 

String answer = "";
String num = "";

for(int i = 0; i < numbers.length; i++) {
    num += numbers[i];
}

char[] list = num.toCharArray();

char max = list[0];
for (int i = 1; i < list.length; i++) {
    if (max < list[i]) {
        max = list[i];
    }
    answer += max;
}

내가 작성한 코드를 살펴보면 numbers에 있는 정수를 문자열로 바꿔주고 char 배열로 만들어줬다. 그런 다음 해당 char [] 배열을 반복문으로 돌면서 정렬하게 만들었는데 문제가 발생했었다.

먼저 데이터가 0으로 들어올 경우 문제가 발생하였고, 10의 자리 숫자를 char로 나누기 때문에 두 개의 문자로 나눠 처리해서 원하는 출력 값을 얻지 못하였다.

 

Comparable과 Comparator

---

Comparable과 Comparator는 둘 다 객체를 정렬하는 데 필요한 메서드(정렬 기준을 제공)를 정의한 인터페이스이다.

두 개의 차이는 Comparator는 기본 정렬 기준 외에 다른 기준으로 정렬하고자 할 때 사용되고, Comparable은 기본 정렬 기준을 구현하는 데 사용된다.

결국 두 개의 인터페이스는 객체를 비교할 수 있도록 만든다는 하나의 목적을 가지고 누구와, 어떻게 비교할 것인지가 나뉘는 것이 핵심이다.

 

Comparable

---

public int compareTo(T o);

Comparable 인터페이스의 핵심은 자기 자신과 매개변수 객체를 비교한다는 것이다.

compareTo 메서드를 잘 보면 int값을 반환하게 되어 있는데 자기 자신과 매개변수 객체를 비교해서 반환 값은 정수 값으로 반환되어야 한다.

그러면 왜 int 값으로 반환되어야 하고, 어떤 기준으로 양수, 0, 음수를 반환할 수 있을까?

다시 강조하면 Comparable 인터페이스의 핵심은 자기 자신과 매개변수 객체를 비교한다는 것을 생각해야 한다.

즉, 자기 자신을 기준으로 상대방(매개변수로 받은 객체)과 대소 관계를 파악하고 그 차이를 반환하게 되는 것이다.

Comparable 인터페이스에서 주의할 점이 하나 있는데 그것은 바로 int 타입의 문제이다. compareTo 메서드는 int 타입으로 반환하기 때문에 해당 범위를 벗어나게 되면 값을 비교할 때 문제가 발생할 수도 있다.

 

 

Comparator

---

int compare(T o1, T o2);

Comparator 인터페이스의 핵심은 두 매개변수 객체를 비교한다는 것이다.

Comparable과 다르게 compare 메서드로 받아온 두 매개변수 객체를 비교하게 된다. 기본적으로 compareTo 메서드와 동작이 같은데 차이가 있다면 자기 자신과 비교되느냐 안되느냐의 차이만 있다.

Comparator도 Comparable과 마찬가지로 int 타입의 범위에 대해서 문제가 발생할 수 있다.

a.compare(b, c)

또 다른 단점으로는 a라는 객체가 compare 메서드를 호출하는데 매개변수로 b와 c를 넘겨주었다. 만약에 a를 가지고 비교하고 싶다면 불필요한 객체를 하나 더 생성해야 되는 단점이 생긴다. 왜냐하면 Comparator는 매개변수로 들어온 객체를 비교하기 때문에 두 객체에 영향을 미치지 comare 메서드를 호출하는 객체에는 아무런 영향을 주지 않기 때문이다.

 

Test t = new Test();
t.compare(a, c)

위의 코드와 같이 a와 c를 비교하기 위해 t라는 Test 객체를 새로 생성해 줘야 되는 단점이 있다. 이러한 문제를 해결하기 위해서 Comparator를 사용할 때 익명 객체(클래스)를 활용하게 된다.

 

MyFunction f1 = new MyFunction() {
    @Override
    public int max(int a, int b) {
        return a > b ? a : b;
    }
};

익명 객체는 새로운 클래스를 만드는 데 이름이 정의되어 있지 않은 것을 말한다. 따라서 이름이 정의되지 않기 때문에 특정 타입이 존재하지 않아 반드시 익명 객체의 경우 상속할 대상이 있어야 한다.

상속은 extends 뿐만 아니라 implements 또한 마찬가지이다. 그럼 이제 Comparator를 익명 객체를 활용하여 사용한다는 것이 Comparator 인터페이스를 구현하여 사용한다는 것으로 이해할 수 있다.

 

public class CompareTest {
    public static void main(String[] args) {
        Comparator<Student> test1 = new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.classNumber - o2.classNumber;
            }
        };
    }

    public static Comparator<Student> test2 = new Comparator<Student>() {
        @Override
        public int compare(Student o1, Student o2) {
            return o1.classNumber - o2.classNumber;
        }
    };
}

 

Comparator를 익명 객체로 만든 코드이다. 이렇게 구현하면 앞서 다른 클래스 내에서 Comparator를 구현할 필요가 없어지고 익명 객체를 저장한 test1이나 test2를 사용할 수 있게 된다.

이제 알고리즘 문제를 풀어보면서 왜 Arrays.sort()를 사용할 때 저렇게 사용하는지 알게 되었다. 다른 문제들도 풀다 보면 Comparator나 Comparable 인터페이스를 사용하는 경우를 종종 봤다.

자바에서는 정렬을 기본적으로 오름차순 정렬을 한다고 하는데 그러면 맨 앞에 위치해야 되는 값이 가장 작은 값이 될 것이다. 그러면 예시로 compare 메서드를 사용한다고 했을 때 매개변수로 받은 두 개의 값을 빼서 음수면 왼쪽 값이 작은 것이므로 정렬하지 않고 양수면 오른쪽 값이 크므로 데이터 교환이 이뤄진다는 것을 알 수 있다.

 

참고 자료

---

나도 아직 완벽하게 정리된 것이 아니기 때문에 밑의 글을 참고해서 공부하는 게 좋을 것 같다. 나 또한 밑의 글을 참고하며 공부해 보면서 정리를 해봤다.

자바 [JAVA] - Comparable 과 Comparator의 이해