programmers) 가장 큰 수

프로그래머스 가장 큰 수

 

이번에는 프로그래머스의 가장 큰 수 문제를 풀어보았다.

 

👉 프로그래머스 가장 큰 수 문제

---

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 구하는 문제이다.

예를 들어 주어진 정수가 아래와 같다면,

[6, 10, 2]

만들 수 있는 수는 다음과 같다.

6102, 6210, 1062, 1026, 2610, 2106

이 중 가장 큰 수는 6210이다.

즉, 배열 numbers가 주어졌을 때 숫자의 순서를 재배치해서 만들 수 있는 가장 큰 수를 문자열로 반환해야 한다.

---

제한 사항

numbers의 길이는 1 이상 100,000 이하
numbers의 원소는 0 이상 1,000 이하
정답이 너무 클 수 있으므로 문자열로 반환

입출력 예시는 다음과 같다.

numbersreturn

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

---

문제 유형 분류

이 문제는 정렬 문제이다.

다만 일반적인 오름차순, 내림차순 정렬이 아니라 직접 정렬 기준을 만들어야 하는 문제였다.

처음에는 숫자를 큰 순서대로 정렬하면 될 것 같았지만, 실제로는 숫자 자체의 크기보다 두 숫자를 이어 붙였을 때 어떤 순서가 더 큰 수를 만드는지를 비교해야 했다.

---

입력 범위 확인

numbers의 길이는 최대 100,000이다.

따라서 모든 순열을 만들어서 가장 큰 수를 찾는 방식은 불가능하다.

예를 들어 숫자가 10개만 있어도 경우의 수가 매우 커지기 때문에, 모든 조합을 직접 확인하는 방식은 사용할 수 없다.

이 문제는 결국 숫자들을 어떤 기준으로 정렬한 뒤 이어 붙이는 방식으로 접근해야 한다.

---

시간 복잡도 허용선 판단

입력 크기가 최대 100,000이므로 O(N^2) 방식은 부담될 수 있다.

정렬을 사용하면 일반적으로 O(N log N)에 해결할 수 있다.

따라서 이 문제는 직접 Comparator 기준을 만들어 정렬하는 방향으로 풀면 시간 복잡도 측면에서 적절하다고 판단했다.

---

처음 생각한 접근

처음에는 단순히 숫자를 큰 순서대로 정렬하면 될 것 같았다.

예를 들어,

[3, 30, 34, 5, 9]

가 있다면 숫자를 내림차순으로 정렬해서 붙이면 되지 않을까 생각했다.

하지만 이 방식은 틀린 접근이었다.

예를 들어 3과 30을 비교해보면 숫자 자체로는 30이 더 크다.

하지만 두 숫자를 이어 붙이면 결과가 달라진다.

3 + 30 = 330
30 + 3 = 303

330이 303보다 크기 때문에, 이 경우에는 3이 30보다 앞에 와야 한다.

즉, 이 문제에서는 숫자 자체의 크기가 아니라,

a + b
b + a

둘 중 어떤 조합이 더 큰지를 기준으로 정렬해야 한다.

---

사용할 자료구조

처음에는 int[] numbers 배열을 바로 정렬하려고 했다.

Arrays.sort(numbers, ...);

하지만 Java에서 int[] 같은 기본형 배열은 Comparator를 사용한 직접 정렬이 불가능하다.

즉, 아래와 같은 방식은 사용할 수 없다.

Arrays.sort(numbers, (a, b) -> b - a);

Comparator를 사용하려면 Integer[], String[], 또는 List<Integer> 같은 객체 형태를 사용해야 한다.

그래서 나는 int[]를 List<Integer>로 변환해서 풀었다.

List<Integer> numbersList = new ArrayList<>();

for (int item : numbers) {
    numbersList.add(item);
}

이번 문제를 풀면서 배열 정렬과 리스트 정렬의 차이도 다시 정리할 수 있었다.

int[] 배열 기본 정렬 → Arrays.sort(numbers)
int[] 배열은 Comparator 사용 불가
List<Integer>는 Comparator 사용 가능
Integer[] 또는 String[]도 Comparator 사용 가능

---

핵심 아이디어

핵심은 두 숫자 a, b가 있을 때 어느 숫자가 앞에 와야 더 큰 수가 되는지 비교하는 것이다.

예를 들어 a = 3, b = 30이라면,

a + b = 330
b + a = 303

이 경우 330이 더 크기 때문에 a가 b보다 앞에 와야 한다.

그래서 정렬 기준은 다음과 같이 잡을 수 있다.

(String.valueOf(b) + String.valueOf(a))
    .compareTo(String.valueOf(a) + String.valueOf(b))

처음에는 Integer.valueOf()로 숫자로 바꿔서 비교하려고 했는데, 이 방식은 위험할 수 있다.

숫자를 이어 붙인 값이 너무 커지면 Integer 범위를 넘어갈 수 있기 때문이다.

이 문제는 최종 결과도 문자열로 반환하는 문제이므로, 굳이 숫자로 바꾸지 않고 문자열끼리 compareTo()로 비교하는 것이 더 안전하다.

---

Comparator에서 헷갈렸던 부분

이번 문제를 풀면서 Comparator가 아직 익숙하지 않다는 것을 느꼈다.

Comparator는 정렬할 때 두 값을 비교해서 어떤 값이 앞에 올지 정하는 규칙이다.

list.sort((a, b) -> {
    return 비교결과;
});

여기서 중요한 점은 a, b가 인덱스가 아니라 리스트 안에 들어있는 실제 값이라는 것이다.

처음에는 이 부분이 헷갈려서 numbersList.get(a)처럼 생각했는데, a와 b는 이미 비교 대상 값이다.

예를 들어 리스트에 아래 값들이 있을 때,

[3, 30, 34, 5, 9]

정렬 과정에서 a = 3, b = 30처럼 실제 값이 들어온다.

그래서 numbersList.get(a)처럼 접근하는 것이 아니라, a와 b를 그대로 사용해야 한다.

---

예외 케이스

주의해야 할 예외 케이스는 모든 숫자가 0인 경우이다.

예를 들어 입력이 아래와 같을 수 있다.

[0, 0, 0]

그냥 이어 붙이면 결과는 "000"이 된다.

하지만 문제에서 원하는 답은 "0"이다.

따라서 정렬 후 만들어진 문자열의 첫 번째 문자가 '0'이라면, 가장 큰 수도 결국 0이라는 뜻이므로 "0"을 반환하도록 처리했다.

return sb.charAt(0) == '0' ? "0" : sb.toString();

---

최종 코드

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        List<Integer> numbersList = new ArrayList<>();

        for (int item : numbers) {
            numbersList.add(item);
        }

        numbersList.sort((a, b) ->
            (String.valueOf(b) + String.valueOf(a))
                .compareTo(String.valueOf(a) + String.valueOf(b))
        );

        StringBuilder sb = new StringBuilder();

        for (Integer number : numbersList) {
            sb.append(number);
        }

        return sb.charAt(0) == '0' ? "0" : sb.toString();
    }
}

---

시간 복잡도

이 풀이에서 가장 시간이 많이 걸리는 부분은 정렬이다.

numbersList.sort((a, b) ->
    (String.valueOf(b) + String.valueOf(a))
        .compareTo(String.valueOf(a) + String.valueOf(b))
);

numbers의 길이를 N이라고 하면 정렬의 시간 복잡도는 일반적으로 다음과 같다.

O(N log N)

Comparator 내부에서는 두 숫자를 문자열로 바꾼 뒤 이어 붙여 비교한다.

a + b
b + a

문제 제한에서 numbers의 원소는 0 이상 1,000 이하이므로 숫자 하나의 길이는 최대 4자리이다.

즉, 문자열을 이어 붙이고 비교하는 비용은 크지 않으며 상수 시간처럼 볼 수 있다.

따라서 전체 시간 복잡도는 다음과 같다.

시간 복잡도: O(N log N)

---

공간 복잡도

공간은 크게 두 곳에서 사용된다.

첫 번째는 int[] numbers를 List<Integer>로 옮기는 부분이다.

List<Integer> numbersList = new ArrayList<>();

입력 배열의 길이가 N이라면, 리스트에도 N개의 값이 들어간다.

두 번째는 결과 문자열을 만들기 위한 StringBuilder이다.

StringBuilder sb = new StringBuilder();

최종 결과 문자열은 모든 숫자를 이어 붙인 길이만큼 공간을 사용한다.

따라서 추가로 사용하는 공간은 입력 크기에 비례한다.

공간 복잡도: O(N)

---

복잡도 정리

시간 복잡도: O(N log N)
공간 복잡도: O(N)

---

이번 풀이에서 배운 점

이번 문제는 단순히 정렬만 하면 되는 문제처럼 보였지만, 실제로는 정렬 기준을 직접 만들어야 하는 문제였다.

특히 아래 내용을 다시 정리할 수 있었다.

int[]는 Comparator 정렬이 불가능하다.
Comparator를 사용하려면 List<Integer>, Integer[], String[] 등을 사용해야 한다.
Comparator의 a, b는 인덱스가 아니라 실제 값이다.
문자열 비교는 compareTo()를 사용한다.
이 문제는 숫자 크기가 아니라 a+b, b+a를 비교해야 한다.
모든 값이 0인 경우에는 "0"을 반환해야 한다.

처음에는 숫자를 큰 순서대로 정렬하면 될 줄 알았다.

하지만 3과 30 같은 예시를 보면서 단순 숫자 비교가 아니라, 두 숫자를 이어 붙였을 때 더 큰 조합이 되는 순서로 정렬해야 한다는 것을 알게 되었다.

이번 문제를 풀면서 Comparator 사용이 아직 익숙하지 않다는 것도 느꼈다.

그래도 여러 방식으로 시도하면서 배열 정렬과 리스트 정렬의 차이, 그리고 Comparator의 동작 방식을 조금 더 이해할 수 있었다.

---

셀프 체크

왜 처음에 바로 풀지 못했는가?

문제 자체의 핵심은 정렬이었지만, 일반적인 숫자 내림차순 정렬로 생각해서 처음 접근이 조금 막혔다.

또 Java에서 Comparator를 사용하는 문법이 익숙하지 않아 여러 번 수정하면서 풀었다.

문제 해석을 잘못했는가?

처음에는 숫자 자체의 크기를 기준으로 정렬하면 된다고 생각했다.

하지만 이 문제는 숫자 크기가 아니라 두 숫자를 이어 붙였을 때 더 큰 조합이 되는 순서를 찾아야 했다.

자료구조 선택을 잘못했는가?

처음에는 int[] 배열을 바로 Comparator로 정렬하려고 했다.

하지만 Java에서 int[]는 Comparator 정렬이 불가능하므로 List<Integer>로 변환해서 해결했다.

엣지 케이스를 놓쳤는가?

모든 값이 0인 경우를 주의해야 했다.

[0, 0, 0]을 그냥 이어 붙이면 "000"이 되기 때문에, 첫 글자가 '0'이면 "0"을 반환하도록 처리했다.

구현 실수가 있었는가?

Comparator 문법에서 실수가 있었다.

특히 a, b를 인덱스처럼 생각하거나, Integer.compare()와 compareTo() 사용법을 헷갈렸다.

이번 풀이를 통해 Comparator는 두 값을 비교해서 정렬 순서를 결정하는 규칙이라는 점을 다시 정리할 수 있었다.