[백준 16496] 큰 수 만들기 - JAVA

문제

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

입력

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

출력

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

---

접근 방법

처음 문제를 접할 때부터 그리디 문제임을 파악할 수 있었고
어떤 기준으로 정렬할지가 가장 중요한 문제였습니다.

처음에는 이렇게 생각했습니다.

• 두 숫자가 같다면 $0$
• 두 숫자를 비교할 때 앞자리부터 비교
  • 한자리씩 비교하면서 각 자릿수 숫자가 달라질 때 큰 숫자를 높은 우선순위로 선정
• 길이가 길거나 짧은 숫자를 선택 (아직 우선 순위 확정 안한 상태)

그러나 첫 번째 입력 예제를 보고 생각이 바뀌게 되었습니다.

$3$과 $30$ 그리고
$3$과 $34$ 를 예시로 들었을 때의 차이였습니다.

$3$과 $30$에서는 $3$이 앞에 오는 것이 더 큰 숫자를 만들 수 있지만
$3$과 $34$에서는 $34$가 앞에 오는 것이 더 큰 숫자를 만들 수 있다는 것을 확인했습니다.

즉, "길이가 작은 숫자를 길이가 긴 숫자의 자릿수만큼 이어붙였을 때
더 큰 숫자가 되는 것이 우선순위가 된다" 라는 개념을 확정하고 정렬 로직을 구현했습니다.

정렬 로직을 너무 어렵게 구현하기 보다는
문자열 $a$와 $b$가 존재할 때

$a + b$를 한 문자열 $AB$와
$b + a$를 한 문자열 $BA$를 비교하는 단순한 방식으로 정렬 로직을 구현했습니다.

추후 최적화를 위해 모듈로 연산을 활용한 자릿수 이어붙이기 방식으로 코드를 개선해볼 예정입니다.

---

코드

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

class CompareString implements Comparable<CompareString> {
    String s;

    public CompareString (String s) {
        this.s = s;
    }

    public int compareTo(CompareString o) {
        return greedy(this.s, o.s);
    }

    private static int greedy(String a, String b) {
        if (a.equals(b)) return 0;

        String AB = a + b;
        String BA = b + a;

        for (int i = 0; i < a.length() + b.length(); i++) {
            if (AB.charAt(i) > BA.charAt(i)) return -1;
            else if (AB.charAt(i) < BA.charAt(i)) return 1;
        }

        return a.length() > b.length() ? 1 : -1;
    }

    @Override
    public String toString() {
        return this.s;
    }
}

public class Main {
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<CompareString> pq = new PriorityQueue<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            pq.offer(new CompareString(st.nextToken()));
        }

        while (!pq.isEmpty()) {
            sb.append(pq.poll());
        }

        System.out.println(sb.charAt(0) == '0' ? '0' : sb);
    }
}