[알고리즘] 가장 큰 수 (Java)

프로그래머스 - 가장 큰 수
문제는 간단하지만 아이디어가 떠오르지 않으면 쉽지 않은 문제이다.

모든 경우의 수를 해보기에는 numbers 배열의 길이가 최대 100,000 까지여서 효율성 테스트에 통과하지 못한다.
10만이면 $O(NlogN)$ 이하로 시간복잡도를 낮춰야 한다.

풀이

어떤 원소를 앞에 놔야하는지 구하기 위해서는 다음과 같은 아이디어가 필요하다.

큰 순서를 구하기 위해 두 원소씩 비교하는데, 각각 문자열로 변환해서 a + b 와 b + a 중에 값이 더 크게 나오는 원소가 앞에 가있으면 그 원소를 결과값에서 앞에 놔야 한다.

예를 들어 10 과 2 중 뭐가 앞에 와야하는지 비교하려면 "102" 와 "210" 중 뭐가 더 큰지 비교하면 된다. "210" 이 더 크므로 무조건 2가 더 앞에 오면 된다.

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
    	// int[] 를 String[] 로 변환하는 부분
        String[] strs = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            strs[i] = Integer.toString(numbers[i]);
        }

		// 핵심 코드
        Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));

		// 원소가 모두 0인 경우 처리 (맨 앞이 0이면 모두 0이라는 뜻이다)
        if (strs[0].equals("0")) {
            return "0";
        }

		// 배열 붙혀서 반환
		return String.join("", strs);
    }
}

(a + b) 와 (b + a) 를 비교하여 배열을 정렬한다. 결과값이 큰게 뒤로 가야하므로 (내림차순) (b + a).compareTo(a + b) 와 비교한다.

String.compareTo()

String 클래스의 public int compareTo(String anotherString) 는 사전순으로 각 문자열의 동일한 위치에 있는 문자(Character)에 해당하는 유니코드 값을 비교해서 그 차이를 반환한다. 첫번째 요소부터 검사하고 동일하지 않으면 바로 반환하므로 문제 요구사항에 적절하다.

숫자 문자를 유니코드로 변환해도 크기 비교는 동일하게 가능하므로 바로 문자열에서 compareTo 를 호출했다.

• 반환값 0 -> 두 문자열이 같음
• 반환값 음수 -> 현재 문자열이 비교 문자열보다 사전순으로 앞에 있음
• 반환값 양수 -> 현재 문자열이 비교 문자열보다 사전순으로 뒤에 있음

Arrays.sort()

Arrays 클래스의 public static <T> void sort(T[] a, Comparator<? super T> c) 는 배열 a 의 요소를 Comparator c를 사용해 정의된 순서에 따라 정렬한다.

Comparator는 두 요소 e1과 e2를 비교해 다음을 반환하는 함수이다.

• 0: e1과 e2는 순서가 동일.
• 음수: e1이 e2보다 앞에 와야 함.
• 양수: e1이 e2보다 뒤에 와야 함.

따라서

Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));

위 코드면 의도한대로 정렬이 된다.

시간복잡도

Arrays.sort() 의 시간복잡도는 O(NlogN) 이고
String.compareTo 는 O(문자열의 길이 = k) 이므로
$O(k * NlogN)$ 이다.
하지만 문제 조건에서 문자열의 길이는 최대 4이므로

해당 문제의 시간복잡도는 $O(NlogN)$ 이다.

Stream 만 사용한 코드

public static String solution(int[] numbers) {
    if (Arrays.stream(numbers).sum() == 0)
        return "0";
    return Arrays.stream(numbers)
            .mapToObj(String::valueOf)
            .sorted((a, b) -> (b + a).compareTo(a + b))
            .collect(Collectors.joining(""));
}

sum, sort, join 모두 스트림 API에 포함되어있으므로 그것을 활용한 깔끔한 코드이다.

다른 풀이

해당 문제의 제출 기록을 보다가 다른 풀이를 발견했다.

Arrays.sort(strs, (a, b) -> (b + b + b).compareTo(a + a + a));

정렬시 비교할 때 요소를 3번 반복한 값을 기준으로 내림차순 정렬한 것이다.

예를 들어 10 과 2 중 뭐가 앞에 와야하는지 비교하려면 "101010" 와 "222" 중 뭐가 더 큰지 비교한 것이다.

문제 요구사항에서 요소를 1000까지만 줬기 때문에 동작하는 알고리즘 같다.
두 방법 모두 되는거같긴 한데 증명은 떠오르지 않아서 쉽지 않은 문제였다.