[백준] 16496번 큰 수 만들기 Java

문제 링크

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

문제

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

입력

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

출력

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

알고리즘: 그리디, 정렬

풀이

먼저 입력받은 수를 자릿수로 구분해서 배열에 저장한다. (정렬할 때 쓰임)
정렬 기준을 세울 때
1. 자릿수 값이 큰 값. ex) 800, 9 -> 첫 번째 수의 0번째 인덱스 8과 두 번째 수의 0번째 인덱스 9는 9가 더 크기 때문에 9, 800으로 정렬

2.자릿수가 전부 같은데 길이가 다른 경우는 앞뒤로 붙여서 더 큰 값을 우선 정렬
ex) 9, 90 -> 두 개의 수의 0번째 인덱스는 같다. (짧은 길이의 수를 기준)
9와 90을 붙이면 990, 90과 9를 붙이면 909 더 큰 값은 990이기 때문에
9, 90 순서로 정렬한다.

위처럼 기준을 세우고 sort 하면 끝이다.

소스 코드

import java.io.*;
import java.util.*;

class NumInfo implements Comparable < NumInfo > {
    long v;
    int pv[];
    public NumInfo(long v, int pv[]) {
        this.v = v;
        this.pv = pv;
    }

    public int compareTo(NumInfo n) {
        int spv[] = this.pv.length <= n.pv.length ? this.pv : n.pv;
        for (int i = 0; i < spv.length; i++) {
            int df = n.pv[i] - this.pv[i];
            if (df > 0) return 1;
            if (df < 0) return -1;
        }
        long tpv = Long.parseLong(String.valueOf(this.v) + String.valueOf(n.v));
        long npv = Long.parseLong(String.valueOf(n.v) + String.valueOf(this.v));
        if (tpv > npv) return -1;
        if (tpv < npv) return 1;
        return 0;
    }
}

public class Main {
    static int N;
    static NumInfo list[];
    static StringBuilder ans = new StringBuilder();
    static boolean all_zero = true;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        list = new NumInfo[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            String s = st.nextToken();
            int pv[] = new int[s.length()];
            for (int j = 0; j < pv.length; j++) {
                pv[j] = s.charAt(j) - '0';
            }
            long v = Long.parseLong(s);
            if (v != 0) all_zero = false;
            list[i] = new NumInfo(v, pv);
        }

        if (all_zero) System.out.println(0);
        else {
            Arrays.sort(list);
            for (int i = 0; i < N; i++) {
                ans.append(list[i].v);
            }
            System.out.println(ans.toString());
        }
    }
}