LeetCode: 179번 (Largest Number) [JAVA]

문제 링크

https://leetcode.com/problems/largest-number/

Largest Number - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 배열에 대한 정렬을 하며, 이 때 정렬 조건은 두 수 a와 b에 대해 ab, ba 형식으로 이어붙인 수 중 더 큰 쪽이 되도록 수를 정렬
2. 전체 배열을 속 0의 개수를 체크한다. 만약 모든 배열이 0이면 단순 0 반환
3. 이후 정렬된 배열을 돌며 문자열로 수를 모두 이어붙여 반환

 문제 속 주어진 int 타입 배열들을 가지고 만들 수 있는 가장 큰 수를 반환해야 한다. 결국 전체 배열을 가지고 정렬을 해야 하는데, 이 때 자바에서 Arrays.sort() 함수를 사용하며 정렬 조건을 명시할 수 있는 Comparator<> 함수를 새로 작성한다. 두 수 a와 b가 주어졌을 때 두 수를 이어붙여 ab, ba 형태로 만든 다음 이 중 더 큰 값이 되게 정렬 조건을 명시한다. 그렇게 배열을 정렬 후 처음부터 배열을 돌며 문자열 형식으로 숫자들을 모두 이어 붙여 반환하면 된다.
 예외적으로 주어진 모든 배열 속 숫자가 0인 경우 "000..."이라는 문자열이 반환될 수 있어 답인 0과 다르기 때문에, 이 부분만을 따로 체크하기 위해 전체 0의 개수를 count하여 모든 배열 요소가 0인지 확인하는 것이 좋다.

 예외로 자바의 경우 int 배열 자체를 직접 만든 정렬 함수를 사용하기 까다로워 우선 Integer 타입으로 래핑작업을 해야 하고, 문자열 연산이 꽤나 느리기 때문에 주어진 숫자들을 최대한 숫자 그대로 활용하여 정렬에 적용하는 것이 좋다.

 

class Solution {
    public String largestNumber(int[] nums) {
        Integer[] numsWrapper = new Integer[nums.length];
        StringBuilder sb = new StringBuilder();
        int zeroCount = 0;

        for (int i = 0; i < nums.length; i++) {//int 배열 -> Integer 배열로 변경
            numsWrapper[i] = nums[i];
            if (nums[i] == 0) {//0의 개수 카운트
                ++zeroCount;
            }
        }

        if (zeroCount == nums.length) {//전부다 0이면
            return "0";
        }

        Arrays.sort(numsWrapper, new Comparator<Integer>() {//배열 sort
            @Override
            public int compare(Integer o1, Integer o2) {
                int o1Length = getLength(o1), o2Length = getLength(o2);
                long a = o1 * (long) Math.pow(10, o2Length) + o2;
                long b = o2 * (long) Math.pow(10, o1Length) + o1;

                if (a >= b) {
                    return -1;
                } else {
                    return 1;
                }
            }
        });

        for (int i = 0; i < numsWrapper.length; i++) {//숫자 모두 합치기
            sb.append(numsWrapper[i]);
        }

        return sb.toString();
    }

    int getLength(int n) {//숫자 자릿수 반환
        int length = 1;

        while (n / 10 != 0) {
            ++length;
            n = n / 10;
        }

        return length;
    }
}

결과