[Java] 프로그래머스 - 가장 큰 수

숫자들을 이어 붙였을 때 가장 큰 수가 되도록 정렬 기준을 직접 설계해야 하는 문제

 

1. 문제 유형

정렬, 문자열, 구현

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 배열의 모든 순서를 직접 만들어서 가장 큰 값을 찾으려고 했다.

오답 원인: 이 문제는 순열로 모든 경우를 확인하는 문제가 아니다.
원소 개수가 최대 100,000개이기 때문에 모든 경우의 수를 만드는 방식은 불가능하다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 숫자 자체의 대소 비교로는 정답을 구할 수 없다. 예를 들면 30은 3보다 크지만, 이어 붙여 보면 330과 303이 되어 3이 앞에 와야 더 큰 수가 된다.

풀이 아이디어:

1. int[]를 String[]로 변환한다.
2. 두 문자열 a, b를 비교할 때 (b + a)와 (a + b)를 비교하는 기준으로 정렬한다.
3. 정렬이 끝난 뒤 앞 원소가 "0"이면 전체가 0으로만 이루어진 경우이므로 "0"을 반환한다.
4. 정렬된 문자열을 순서대로 이어 붙여 최종 결과를 리턴한다.

4. 구현 코드

import java.util.*;

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

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

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

        if (strArray[0].equals("0")) {
            return "0";
        }

        StringBuilder answer = new StringBuilder();

        for (int i = 0; i < strArray.length; i++) {
            answer.append(strArray[i]);
        }

        return answer.toString();
    }
}

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

---

 

인사이트

• 보통 정렬은 숫자 크기나 사전순으로만 생각했는데 이번 문제를 통해 문제에 맞는 새로운 정렬 기준을 직접 만들 수 있다는 점을 체감했다.
• (b + a)와 (a + b)를 비교하는 방식은 단순해 보이지만 이 문제의 핵심 로직이 전부 담겨 있는 부분이다.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42746