Java] Programmers 가장 큰 수

지문

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbersreturn

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

해법

1. 주어진 순자를 각각 문자열로 변경하여 저장한다.

2. 저장한 문자열을 정렬한다

3. 정렬된 문자열을 이어 붙인 후, 반환한다.(결과가 "0000" 등 0의 연속일 경우, 0 하나만 출력하도록 예외처리도 한다)

 

해법은 굉장히 심플하지만, '2. 저장한 문자열을 정렬한다' 부분에서 '어떻게 정렬할 건데?'라는 고민을 이전에 비슷한 문제를 풀어본 경험이 없다면 생각해내기 힘드실 겁니다. 괜찮아요. 이제 알면 되죠.

제가 해결한 방법으로 풀기 위해서는 StringBuffer 클래스와 Comparator 인터페이스를 먼저 알고 계셔야 하는데, 두 개념에 대한 설명은 여기서 따로 다루지는 않고, 아직 잘 모르신다면 선행 학습이 필요합니다.

저는 성능을 위해 StringBuffer를 이용했지만, 편의성을 위해 String을 기준으로 설명드리자면, 만약 다음과 같이 두 변수가 있다고 가정해 봅시다.

String o1 = "123";

String o2 = "132";

Comparator 인터페이스 내 compare 함수의 정렬하는 기준을 o1 + o2.compare(o2 + 1)과 같이 하게 되면

o1 + o2 = "123132"

o2 + o1 = "132123"

이 됩니다. 그리고 두 문자열을 비교했을 때 "132123"이 "123132"보다 크죠. 이 기준으로 정렬을 합니다.

예시는 String으로 들었지만, StringBuffer가 성능이 더 좋으니 이를 StringBuffer로 변경합니다.

정렬을 위한 코드는 다음과 같습니다.

Arrays.sort(arr, new Comparator<StringBuffer>() {
            @Override
            public int compare(StringBuffer o1, StringBuffer o2) {
                return (new StringBuffer(o2.toString() + o1.toString()).compareTo(new StringBuffer(o1.toString() + o2.toString())));
            }
        });

이 부분을 제외하고는 크게 어려울 부분은 없다고 생각합니다.

전체 코드

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        StringBuffer[] arr = new StringBuffer[numbers.length];

        for (int i = 0; i < numbers.length; i++) {
            arr[i] = new StringBuffer();
            arr[i].append(String.valueOf(numbers[i]));
        }

        Arrays.sort(arr, new Comparator<StringBuffer>() {
            @Override
            public int compare(StringBuffer o1, StringBuffer o2) {
                return (new StringBuffer(o2.toString() + o1.toString()).compareTo(new StringBuffer(o1.toString() + o2.toString())));
            }
        });

        for (int i = 0; i < arr.length; i++) {
            //System.out.println(arr[i]);
            answer += arr[i];
        }

        boolean bZero = true;
        for (int i = 0; i < answer.length(); i++) {
            if (answer.charAt(i) != '0') {
                bZero = false;
                break;
            }
        }

        if (bZero) {
            return "0";
        } else {
            return answer;
        }
    }
}

 

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수