프로그래머스 - 가장 큰 수 (JAVA)

프로그래머스 가장 큰 수 풀이 과정
스스로 풀지 못했다. 접근 방향은 두 번 바꿨는데 둘 다 코드로 구현하지 못했다.
과거 코드(남의 코드)를 참고해서 정답을 냈고, 핵심 로직을 이번에 제대로 이해했다.
총 1번의 제출

---

처음엔 만들 수 있는 모든 숫자를 ArrayList에 넣고 내림차순 정렬하면 가장 큰 수가 맨 앞에 오지 않을까라고 단순하게 접근했다.
근데 모든 경우의 수는 배열 길이에 따라 너무 커지고, 반복문으로 모든 조합을 만드는 방식 자체가 머릿속에서 정리가 안 됐다.

두 번째로 생각한 방법은 정렬 기준 자체를 정의하는 거였다.
길이가 같으면 내림차순, 길이가 다르면 두 자리 수의 일의 자리와 한 자리 수를 비교해서 정렬하는 방식이었는데,
이것도 코드로 구현하기엔 너무 복잡했다.

결국 과거에 참고했던 남의 코드를 다시 꺼냈다. 근데 여전히 핵심 로직이 이해가 안 됐다.
이번 기회에 제대로 뜯어봤다.

---

1트 (정답, 남의 코드 참고)

→ int[]를 String[]으로 변환한다.
→ 두 문자열 s1, s2를 이어 붙인 결과를 비교해서 정렬 순서를 정한다.
→ (s2+s1).compareTo(s1+s2) — 이게 핵심이다.
→ 모든 값이 "0"이면 "0" 반환, 아니면 정렬된 순서대로 이어 붙인다.

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] array = new String[numbers.length];

        for(int i=0; i<numbers.length; i++) {
            array[i] = String.valueOf(numbers[i]);
        }

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

        if(array[0].equals("0")) return "0";

        String answer = "";
        for(String s : array) answer += s;

        return answer;
    }
}

핵심 로직 이해 — (s2+s1).compareTo(s1+s2)

이게 왜 동작하는지가 이 문제의 전부다.

예를 들어 s1 = "3", s2 = "30"이라고 해보자.

• s1 + s2 = "330"
• s2 + s1 = "303"

둘 중 어떤 순서로 붙여야 더 큰 수가 될까?
"330" > "303" 이니까 s1이 앞에 와야 한다.

compareTo는 (s2+s1)이 (s1+s2)보다 작으면 음수를 반환한다.
Arrays.sort는 음수가 나오면 s1을 앞에 유지한다.
즉, 두 문자열을 이어 붙였을 때 더 큰 쪽이 앞에 오도록 정렬되는 것이다.

s1	s2	s1+s2	s2+s1	앞에 와야 할 것
"3"	"30"	"330"	"303"	s1 ("3")
"9"	"5"	"95"	"59"	s2 ("9")
"34"	"3"	"343"	"334"	s1 ("34")

내가 두 번째로 시도했던 "길이가 다르면 일의 자리를 비교하자"는 방향은 사실 이 로직이 해결하는 문제와 같은 문제를 풀려고 한 거였다. 근데 직접 비교 조건을 나열하려다 보니 케이스가 너무 많아졌던 것이고, 이 코드는 그냥 붙여보고 더 큰 쪽을 앞에 놓는다 는 단순한 아이디어로 모든 케이스를 한 번에 해결한 거다.

위 풀이의 결과

• 정렬 기준을 직접 정의하는 Comparator를 활용한 풀이다.
• array[0].equals("0") 체크는 입력이 [0, 0, 0]처럼 전부 0인 경우 "000" 대신 "0"을 반환하기 위한 처리다.
• 코드 자체는 짧지만, (s2+s1).compareTo(s1+s2) 라는 발상을 스스로 떠올리기가 쉽지 않다.

---

이 문제는 솔직히 스스로 못 풀었다.
첫 번째 접근(모든 경우의 수)은 방향 자체가 틀렸고, 두 번째 접근(직접 비교 조건 나열)은 방향은 맞았지만 구현을 못 했다.
핵심 아이디어인 "두 수를 이어 붙여서 더 큰 쪽이 앞에 오도록 정렬한다" 는 발상은 이번에 제대로 이해했다.
다음에 비슷한 문제가 나오면 바로 Comparator에서 두 원소를 조합해서 비교하는 방식을 먼저 떠올릴 수 있을 것 같다.