[Algorithm] 프로그래머스: 가장 큰 수

이 글은 프로그래머스 - 정렬 part의 "가장 큰 수" 문제를 풀다가 새로 알게 된 내용을 정리한 글입니다.

이 문제의 핵심은 compareTo() 메소드와 Comparator<T>라고 생각한다.

사실 여태 compareTo()를 막연하게 문자열의 대소비교를 정수형으로 반환해주는 것으로 알고있었지만, 실제로 써 본 적이 없어 동작원리가 어떻게 돌아가는지 자세히 알지 못했다.
마찬가지로 Comparator는 많이 보기만 봤지, 실제로 써본 적이 없어 무엇인지 잘 몰랐었다.
하지만 이 문제 덕분에 조금이나마 알게 되어 정리를 해보겠다.

우선 문제를 정리해보자면, 숫자들이 주어지면 이 숫자들을 적절히 배치하여 만들 수 있는 수 중에서 가장 큰 수를 구하는 것이다.

나는 이 문제를 해결하기 위해 숫자들을 오름차순 혹은 내림차순으로 우선 정렬 후 하나씩 비교해가며 붙여나가는 것을 생각해보았다.

하지만 이 아이디어의 문제는 6 10 2 에서 바로 발견할 수 있다.

오름차순으로 정렬 시, 2 6 10이다. 이제 앞에서부터 하나씩 붙여나가면 6210이 나오지만,
내림차순으로 정렬 시, 10 6 2이다. 이제 앞에서부터 하나씩 붙여나가면 6102가 나온다.

그래서 999~0, 1000부터 하나씩 내려오면서 numbers에 있는 값들을 비교하여 numbers에 있는 수들을 하나씩 붙이고 비교해나가는 방법도 생각해보았지만 이는 너무 비효율적이라 pass

그래서 도저히 해결 아이디어가 생각나지 않아 구글링을 했다.

import java.util.*;

class Solution {
	public String solution(int[] numbers) {
    
		String[] result = new String[numbers.length];
		for (int i = 0; i < numbers.length; i++)
			result[i] = Integer.toString(numbers[i]);

		// 정렬
		Arrays.sort(result, (s1, s2) -> (s2 + s1).compareTo(s1 + s2));

		// 0만 여러개 있는 배열의 경우 하나의 0만 리턴
		if (result[0].equals("0")) {
			return "0";
		}

		String answer = "";
		for (String a : result)
			answer += a;
        
		return answer;
	}
}

여기서 핵심은 numbers를 String으로 변환하여 정렬을 하는 것이다.
처음 이 코드를 봤을 때 정수랑 문자열이 비교하는 데에 있어서 무슨 차이를 보이는지 몰랐다.

하지만 그 바로 밑 정렬 코드에서 정렬 기준이 되는 (s1, s2) -> (s2 + s1).compareTo(s1 + s2)를 보면 이해할 수 있다.

우선, Arrays.sort(T[] a, Comparator<? super T> c) 를 알아보자.
두 번째 파라미터로 Comparator<> c를 받는다. 이것이 바로 정렬 기준이 되는데,

위의 해답코드를 보면 람다식으로 (s1, s2) -> (s2+s1).compareTo(s1+s2) 이 부분을 구체화하면 사실 이런 코드가 된다.

Arrays.sort(result, new Comparator<String>() {
	@Override
    public int compare(String s1, String s2) {
    	return (s2+s1).compareTo(s1+s2);
    }
}

(s2+s1)과 (s1+s2)를 비교해서, 만약 (s2+s1) > (s1+s2)이라면 s1과 s2의 자리를 바꾼다.
최종적으로, 두 문자열을 합쳐서 비교했을 때의 오름차순? 으로 정렬된다.

자리비교 내용추가) s1과 s2가 있으면, 두 문자열을 합했을 때, s2가 먼저 나오게 합치는 것이 크면, s1과 s2의 자리를 바꾸어라

이제 이 문자열들을 앞에서부터 순서대로 붙여나가면 끝이다.

하지만 예외의 경우로, 0만 여러 개 있는 경우가 있을 수 있다.
이 경우에는 맨 앞에 "0"이 오기에 이런 점을 이용해서 answer에 "0"을 대입한다.