BOJ 16496 큰 수 만들기

https://www.acmicpc.net/problem/16496

문제

음이 아닌 정수가 N개 들어있는 리스트가 주어졌을 때, 리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나머지 수는 0으로 시작하지 않으며, 0이 주어지는 경우 0 하나가 주어진다.

---

출력

리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 출력한다. 수는 0으로 시작하면 안되며, 0이 정답인 경우 0 하나를 출력해야 한다.

---

예제 입력 1

5
3 30 34 5 9

예제 출력 1

9534330

예제 입력 2

5
0 0 0 0 1

예제 출력 2

10000

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        /**
         * 입력받은 수를 나열해야 하기 때문에 그냥 String 형으로 입력받는다.
         * 두 수를 이어붙였을 때, 앞에 붙였을 때 더 큰 수가 나오는 수를 먼저 뽑기 위한 우선순위 큐
         */
        PriorityQueue<String> queue = new PriorityQueue<>((s1, s2) -> {
            if((s1 + s2).compareTo(s2 + s1) > 0) return -1;
            return 1;
        });
        for (int i = 0; i < N; i++) queue.offer(st.nextToken());

        // 차례로 우선순위 큐에서 수를 뽑아 정답 문자열에 추가
        StringBuilder answer = new StringBuilder();
        while (!queue.isEmpty()) answer.append(queue.poll());

        /**
         * 수가 0으로 시작하는 경우는, 모든 수가 0일 경우 밖에 없기 때문에
         * 생성된 수가 전부 0으로만 이루어져 있을 때, 정답 문자열을 "0"으로 초기화
         */
        int i = 0;
        for (; i < answer.length() && answer.charAt(i) == '0'; i++) ;
        if(i == answer.length()) answer = new StringBuilder("0");
        System.out.println(answer);
    }
}