Today's Algorithm(2019-01-08)

programmers. 가장 큰 수

이전에 풀어봤던 문제인데요. 그 때 아마 제 힘으로 못 풀고 다른 사람의 코드를 참고했던 것 같습니다. 이전에 정리한 적이 없어서 다시 한번 풀어보았는데요. 아이디어가 기억이나서 다행이지 만약 기억이 나지 않았다면 어렵게 풀었을 것 같아요.

 

이 문제에서 일반 문자열 정렬로 되지 않는 부분이 다음과 같은 예 입니다.

int[] numers = {3, 30, 34, 5, 9};

문자열 정렬로 하면 9, 5, 34, 30, 3으로 정렬이 되겠지만 사실 가장 큰 수가 나오기 위해선 9, 5, 34, 3, 30 으로 되어야하거든요. 그래서 앞자리가 같은 경우엔 추가적으로 정렬을 해줘야합니다. 그리고 그 부분이 포인트인데요. 그 부분은 코드로 살펴볼게요.

 

class Solution {
    public String solution(int[] numbers) {
        List<String> texts = new ArrayList<>();

        for (int number : numbers) {
            texts.add(String.valueOf(number));
        }
        Collections.sort(texts, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if(o1.charAt(0) == o2.charAt(0)) {
                    int num1 = Integer.valueOf(o1 + o2);
                    int num2 = Integer.valueOf(o2 + o1);
                    return num2 - num1;
                }
                return o2.compareTo(o1);
            }
        });

        StringBuilder sb = new StringBuilder();
        for (String text : texts) {
            sb.append(text);
        }

        return sb.charAt(0) == '0'? "0" : sb.toString();
    }
}

12, 13줄에서 제가 고민했던 부분이 처리가 되고 있는데요. 만약 앞자리 수가 같은 경우엔 앞, 뒤 조합으로 Integer 타입의 2개의 수를 만든다음 그것의 대소를 비교하는 것입니다. 그렇게 저희가 의도했던 바와 같이 정렬이 될 것입니다.

 

마지막으로 수가 0, 0, 0, 0이 주어지면 답이 0으로 반환되어야 하는데 25줄에서의 처리가 없을 때는 0000으로 반환될 것입니다. 그렇기 때문에 이 부분을 처리해주기 위해 가장 앞자리수가 0이면(젤 앞자리가 0이면 뒷에 수는 볼 필요없이 0일 것입니다) 그냥 "0"으로 반환할 수 있도록 하였습니다.