[Programmers] 가장 큰 수 문제 풀이

# 프로그래머스 가장 큰 수

배열의 요소들을 연결하여 만들 수 있는 숫자 중 가장 큰 숫자를 구하는 문제이다.

배열의 요소를 내림차순으로 정렬하면 가장 큰 숫자를 구할 수 있는데, 비교 방법이 조금 특이하다. 일반적인 숫자 비교를 생각해보자. 12는 2보다 크다. 그런데, 12와 2를 조합하여 만들 수 있는 숫자는 122, 212가 있으며 212가 더 큰 숫자가 된다.

그런데, 이 문제에서는 일반적인 숫자 비교가 아닌 숫자로 이루어진 문자열을 비교하는 것처럼 자리수의 대소비교가 필요하게 된다. 문제에서 주어진 컨텍스트에 의해 각 숫자는 0 이상, 1000 이하로 최대 4개의 자리수를 가질 수 있다. 나누기와 나머지 연산자를 이용하여 각 자리수를 비교할 수도 있지만 나는 숫자를 문자열로 변환하여 split 하는 방식을 사용했다. 먼저 코드를 살펴보자.

private String largestNumber(int[] numbers) {
    if (Arrays.stream(numbers).allMatch(s -> s == 0)) return "0";
    return Arrays.stream(numbers)
        .boxed()
        .map(n -> String.valueOf(n))
        .sorted((o1, o2) -> {
            String[] split = o1.split("");
            String[] split1 = o2.split("");

            String o1s = "";
            String o2s = "";
            for (int i = 0; i < 4; i++) {
                o1s += i < split.length ? split[i] : split[i % (split.length)];
                o2s += i < split1.length ? split1[i] : split1[i % (split1.length)];
            }
            return o2s.compareTo(o1s);
        })
        .collect(Collectors.joining());
}

각 배열 요소를 문자열로 변경하여 조금 특이한 방식으로 정렬을 수행한 뒤, 문자열을 연결하면 최대값이 된다. 정렬에 사용된 대소비교 방식을 살펴보자.

assertThat(largestNumber(new int[]{12, 121})).isEqualTo("12121");

먼저 테스트 케이스이다. 12와 121을 비교하면 12를 더 큰 숫자로 취급해야 한다. 이를 해결하는 방법은 자리수가 최대 4자리라는 컨텍스트에서 힌트를 얻을 수 있다.

• 모든 숫자를 4자리 숫자로 취급한다.
  • 해당 자리의 숫자가 같은 경우, 다음 자리수를 비교한다.
  • 배열 요소의 자리수보다 큰 자리수의 경우 (자리수의 index) mod 숫자의 길이를 이용하여 구한다.
    • Ex) 12는 12가 반복되어 12121212, 121은 121이 반복되어 121121121
• 12는 1212가 되며 121는 1211가 된다.
  • 1212 > 1211이므로 12가 121보다 앞자리에 위치하게 된다.

assertThat(largestNumber(new int[]{21, 212})).isEqualTo("21221");

위 테스트 케이스도 마찬가지이다. 21(2121)과 212(2122)를 비교하여 212를 앞자리에 위치시키면서 21221를 만든다. (21221 > 21212)

assertThat(largestNumber(new int[]{0, 0, 0, 0})).isEqualTo("0");
// if (Arrays.stream(numbers).allMatch(s -> s == 0)) return "0"; 필요

모든 숫자가 0일 수도 있는데 각 숫자를 문자로 취급하여 join하였으므로 위 테스트 케이스에서는 "0000"이 반환된다. 이는 모든 숫자가 0인 경우 "0"을 반환하는 경계를 추가하여 해결한다.