[백준 Baekjoon] 1422번 숫자의 신 - JAVA

문제 풀이

유의사항

1. 각 수는 1,000,000,000의 크기로 문자열을 사용하여 이어 붙여야 한다.

(자바의 문자열은 compareTo() 함수를 사용하여 비교가 가능하다.)

2. 숫자가 중복될 수 있으므로 가장 큰 수를 찾아 반복할때 유의해야한다.

 

정렬만 잘하면 쉽게 해결할 수 있는 문제이다. 두 수를 붙였을때 어떤 숫자가 더 큰지를 기준으로 정렬을 해야한다.

Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

위의 정렬식을 보면 o2 + o1과 o1 + o2를 비교하여 정렬을 수행한다.

이어 붙였을때 가장 큰 수를 찾고, 반복해야할 수를 찾아 순서대로 합치는것으로 정답을 찾을 수 있다.

 

문제의 예제 3을 예시로 들면 o1을 1, o2를 10이라 했을 때, o2 + o1 = 101, o1 + o2 = 110이다. 이 경우 110이 더 큼으로 1이 앞에 오게 되고 다음으로 10이 온다. 정렬을 하면 1, 10, 100 순으로 정렬된다.

 

입력을 받을때 max로 가장 큰 수를 저장한다. K보다 N이 큰 경우 반복할 수 이다.

 

이제 정렬된 문자열 배열을 순회하며 이어 붙인다.

입력에서 찾은 가장 큰수의 경우는 K - N만큼 반복하여 이어 붙인다. 이 때 중복된 수가 가장 큰 수가 될 수 있으므로 flag를 두어 검사한다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        String[] arr = new String[K];
        int max = 0;

        for (int i = 0; i < K; i++) {
            arr[i] = br.readLine();
            max = Math.max(max, Integer.parseInt(arr[i]));
        }

        Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

        boolean flag = true;

        StringBuilder answer = new StringBuilder();
        for (String t : arr) {
            answer.append(t);
            if (max == Integer.parseInt(t) && flag) {
                for (int i = K; i < N; i++) {
                    answer.append(t);
                    flag = false;
                }
            }
        }

        System.out.println(answer);
    }
}