프로그래머스 가장 큰 수 자바 풀이

문제 링크

문제 요약

0 또는 양의 정수 배열이 주어진다
배열의 숫자를 순서대로 이어 붙여 만들 수 있는 가장 큰 수를 문자열로 반환한다
정답이 클 수 있어서 문자열로 반환한다

문제 풀이

처음에는 숫자를 그냥 큰 값부터 정렬해서 이어 붙이면 될 거라 생각했다.

하지만 이 방식은 틀렸다.

문제에 나온 예시처럼 [3, 30, 34, 5, 9]에서 숫자 크기로만 정렬하면 9, 5, 34, 30, 3 순서가 되어 9534303이 나온다.

하지만 실제 정답은 9534330이다. 30과 3처럼 자리수가 다른 두 수는 숫자 크기 비교로 순서를 정할 수 없다.

이 문제의 핵심은 두 숫자를 이어 붙였을 때 어느 순서가 더 큰 값을 만드는지로 비교해야 한다는 점이다.

a와 b 두 수를 비교할 때 a+b와 b+a를 문자열로 만들어 비교하면 된다.

b+a가 더 크면 b가 앞에 와야 한다
그렇게 정렬한 뒤 순서대로 이어 붙이면 가장 큰 수가 만들어진다

정렬 후 가장 앞자리가 "0"이면 나머지도 전부 0이라는 뜻이므로 "0" 하나만 반환한다.

최종 코드

java

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] values = new String[numbers.length]; // 이어붙이기 비교를 위해 문자열로 다룬다

        for (int i = 0; i < numbers.length; i++) { // 각 숫자를 문자열로 변환
            values[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(values, (a, b) -> (b + a).compareTo(a + b)); // b+a 가 a+b 보다 크면 b를 앞에 오도록 정렬
        if (values[0].equals("0")) { // 가장 큰 자리가 0이면 전부 0이라는 뜻
            return "0";
        }

        StringBuilder result = new StringBuilder();

        for (String value : values) { // 정렬된 순서대로 이어 붙인다
            result.append(value);
        }

        return result.toString();
    }
}

가장 큰 수

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기