백준 16496 자바 - 큰 수 만들기 (boj 16496 java)

문제 : boj16496

 

  당연한거지만 앞에 올수록 더 전체값이 커질만한 순서대로 정렬한 후, 출력해주면 되는 문제이다. 그 정렬 규칙만 잘 정하면 된다.

 

케이스1 - 예를들어 9와 89999999가 있다. 직관적으로 자리수와 정렬 규칙은 관계가 없음을 알 수 있다. 둘 중 작은 길이의 숫자까지 비교해서 그 중 다른 숫자가 있다면 쉽게 규칙을 정할 수 있다. 이 경우 9를 먼저 놓는것이 당연히 이득이다.

 

케이스2 - 그럼 98와 98999이 있다면 어떨까? 직관적으로 98999를 먼저 두는 것이 이득임을 알 수 있다. 이 경우는 '케이스1'로는 판단할 수 없는 경우이다. 그렇다면 자리수가 다르면서, 둘 중 작은 자리수까지 비교해도 비교가 안되는 경우를 어떻게 판단할지가 관건임을 알 수 있다.

 

  내 경우 규칙을 아래와 같이 정했다. 두 수의 최소공배수까지 서로 반복하면서 살펴보는 것이다. 예를들어 '케이스2'의 경우 아래와 같이 비교하면 된다.

  참고로 최소공배수를 구하기 위해 최대공약수를 구하는 것 보다, 그냥 공배수(첫번째 수의 길이 * 두번째 수의 길이) 만큼 비교해보는게 약간 더 빠르긴 했다. 그래서 이하 코드는 최소공배수를 따로 구하지 않고 진행했다. 그리고 저렇게 반복하는 것은 뭐 배열에 직접 반복해서 기입한 후 비교해도 되겠지만, 나머지 연산을 사용하면 자동으로 반복시킬 수 있다. 이하의 코드를 참고하면 된다.

char c1 = this.n.charAt(i%this.n.length());
char c2 = o.n.charAt(i%o.n.length());

 

  정렬 규칙대로 정렬 방식을 구현한 후(자바의 경우 Comparable 또는 Comparator를 구현하면 된다.), 해당 규칙대로 정렬하고 차례대로 출력해주면 답이 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    class Num implements Comparable<Num> {
        String n;
        public Num(String n) {
            this.n = n;
        }

        @Override
        public int compareTo(Num o) {
            for (int i = 0; i < this.n.length()*o.n.length(); i++) {
                char c1 = this.n.charAt(i%this.n.length());
                char c2 = o.n.charAt(i%o.n.length());
                if (c1 == c2) continue;
                chk = true;
                return c2-c1;
            }
            return 0;
        }
    }
    boolean chk = false;
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Num> arr = new ArrayList<>(n);
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (n-->0) arr.add(new Num(st.nextToken()));
        Collections.sort(arr);
        if (!chk && arr.get(0).n.equals("0")) {
            System.out.println("0");
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.size(); i++) {
            String cur = arr.get(i).n;
            for (int j = 0; j < cur.length(); j++) {
                sb.append(cur.charAt(j));
            }
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}