백준 알고리즘 1422번: 숫자의 신

문제 정보

---

1422번: 숫자의 신

 

핵심

---

수들을 어떻게 정렬할 것인가

 

문제를 요약하자면, K개의 자연수 중 N개를 뽑아 붙여서 만들 수 있는 수 중 가장 큰 수를 만드는 것이다

• 같은 수는 여러번 이용 가능하지만, 모든 수는 적어도 한번씩 이용하여야 한다
• 각 수는 1,000,000,000 보다 작거나 같다
• K <= 50, N <= 50, K <= N

 

먼저 바로 떠올릴 수 있는 부분은 다음과 같았다

• K개의 수들 중 N개의 수를 뽑을 때, 한번씩 뽑고 남은 N-K개의 수는 K개의 수 가운데 가장 큰 수를 택하면 된다
  • 큰 수를 더 많이 뽑는 것이 어느 면에서나 이득이다. [2, 3, 7] 에서 4개를 뽑으면 7을 2번 뽑을 것이다.

 

정렬의 경우, 우선순위 큐를 사용하여 받은 문자열(String)을 정렬해 주었고

그리고 정렬에 관한 문제를 세 부분으로 구성하였다

	@Override
	public int compare(String o1, String o2) {
		// o2 o1의 길이가 서로 같은 경우
		if(o1.length() == o2.length()) {
			return Integer.parseInt(o2) - Integer.parseInt(o1);
		}
		// o2 o1의 길이가 서로 다른 경우
		int minLength = Math.min(o1.length(), o2.length());
		for(int i=0; i<minLength; i++) {
			if(o1.charAt(i) == o2.charAt(i)) {
				continue;
			}
			return Character.getNumericValue(o2.charAt(i)) - Character.getNumericValue(o1.charAt(i));
		}
		// 길이가 서로 다르고, 2개의 수 중 작은 길이의 수만큼이 동일한 경우
		String a = o1 + o2;
		String b = o2 + o1;
		return Long.parseLong(a) > Long.parseLong(b) ? -1 : 1;
	}

마지막에서, 길이가 다르고 작은 길이의 수만큼이 동일한 경우 (123, 12)

이런 경우에서 어떤식으로 두 수의 대소를 비교해야 좋을 지 생각해 보다가

 

21 212
// answer : 21221 (212/21)

232 23
// answer : 23232 (23/232)

이 해당 케이스를 보고

아 이건 합쳐서 비교해야 되겠구나.. 라고 생각이 들어서

두 수를 서로 교차하여 합친 수를 두개 만들고(a+b, b+a) 이를 비교하여 순서를 결정해 주었다

 

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
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());

        Queue<String> queue = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                // o2 o1의 길이가 서로 같은 경우
                if(o1.length() == o2.length()) {
                    return Integer.parseInt(o2) - Integer.parseInt(o1);
                }
                // o2 o1의 길이가 서로 다른 경우
                String a = o1 + o2;
                String b = o2 + o1;
                return b.compareTo(a);
            }
        });
        int max = 0;
        for(int i=0; i<K; i++) {
            String input = br.readLine();
            queue.add(input);
            max = Math.max(max, Integer.parseInt(input));
        }
        for(int i=0; i<N-K; i++) {
            queue.add(String.valueOf(max));
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++) {
            sb.append(queue.poll());
        }

        System.out.println(sb);
    }
}

 

Source Code on GitHub

---