백준 1038 감소하는 수 Java

알고리즘 분류 브루트 포스, 다이나믹 프로그래밍으로 분류되어있는 감소하는 수 문제이다.

브루트 포스로 짜봐도 시간 초과가 나오고 jump 변수를 사용해서 필요없는 수는 건너뛰는 다른분들의 코드를 봐도 제대로 이해하기가 쉽지 않았다. dp는 더더욱... 그렇다. 그래서 이 문제는 Queue를 활용하여 푸는 방법이 제일 간단하고 쉬운 것 같다.

문제를 읽어보면 N이 0부터 9까지 인 경우에는 그냥 N을 출력해주면 된다. 그리고 감소하는 수가 없다면 -1 출력인데 여기서 수는 무한한데 어떻게 감소하는 수가 없을 수 있을까 하는 의문이 들 수 있다.

N은 백만까지이지만 이것도 함정이다..

생각해보면 감소하는 수는 9876543210보다 큰 수가 있을 수 없다. 그리고 9876543210은 1022번째 감소하는 수이다. 고로 N이 1022보다 크다면 -1을 출력하면 된다.

N제한이 백만까지인데 1022보다 N이크면 감소하는 수가 없는 것이므로 전부 -1 출력이라는 말이다.

문제의 해결 방법은 먼저 1부터 9까지 차례대로 Queue에 넣어준 다음 큐에서 poll한 수를 k에 저장하고 k % 10 한 결과를 temp에 저장한다. (temp에는 k의 맨 마지막 자리가 저장된다.)

for문을 0부터 9까지 돌려서 temp보다 작다면 i가 작다면 k에 10을 곱한 후 i를 더하고 다시 큐에 넣으면 된다. 이 과정을 카운트가 N이 될 때까지 반복하면 된다.

코드를 보면 바로 이해할 수 있을 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Q1038 {

    public static void main(String[] args) throws IOException{
        int n = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
        if(n>1022) {
            System.out.println(-1);
        } else if(n<10) {
            System.out.println(n);
        } else {
            Queue<Long> q = new LinkedList<>();
            int cnt= 0;
            for(int i=1; i<10; i++) {
                q.add(new Long(i));
                cnt++;
            }
            while(cnt<n) {
                long k = q.poll();
                long temp = k % 10;
                for(int i=0; i<temp; i++) {
                    q.add(k*10 + i);
                    cnt++;
                    if(cnt == n) {
                        System.out.println(k*10+i);
                        break;
                    }
                }
            }
        }
    }
}

이 문제가 헷갈리는 점은 감소하는 수의 최대값이 1022번째 감소하는 수라는 점과 감소하는 수의 최대값이 int의 MAX_VALUE값을 넘어가므로 Long을 써야 한다는 점이다.

물론 큐를 사용해서 감소하는 수를 찾아내는 과정도 어렵고 헷갈린다.