[백준 알고리즘] Q1038 감소하는수 - 큐

1. Java 구현

            
package Q1038;

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

public class Main {

    public static void main(String[] args) throws IOException {
        System.out.println(solve(new Scanner(System.in).nextInt()));
    }

    public static String solve(int n) {
        if(n < 10)
            return String.valueOf(n);

        Queue decreases = new LinkedList<>();
        for (int i = 0; i < 10; i++)
            decreases.add(String.valueOf(i));

        int result = 9;
        while(!decreases.isEmpty()) {
            String extract = decreases.poll();
            for (int i = 0; i < (extract.charAt(extract.length() - 1) - '0'); i++) {
                decreases.add(extract + i);
                result++;
                if(result == n)
                    return extract + i;
            }
        }

        return String.valueOf(-1);
    }
}

2. 코드설명

 처음에는 0부터 순차적으로 증가시켜서 감소하는 수인지 확인하는 방식으로 풀었다. 당연히 시간초과가 났다. 이 문제의 핵심은 두 가지이다.

 첫번째는, 감소하는수를 발견하는 과정을 반복하는 횟수를 최소화하는 것이다. 그래서 큐 자료구조를 사용했다.

 큐에는 감소하는 수만 넣게 한다. 그리고 그것을 하나씩 꺼내고 꺼낸 숫자의 뒷자리보다 작은 것을 하나씩 더한다.

 예를들어 543은 감소하는 수이기 때문에 큐에 들어있을 것이고, 그 수를 꺼내서 543의 뒷자리 3보다 작은 숫자를 하나씩 더한다. 그러면 5431 5432 라는 감소하는 수가 발생하고,

 그 수를 큐에 넣는다. 이와 같은 작업을 반복하는 것이다. 그러면 불필요한 반복문을 돌지 않고, 감소하는 수에 해당하는 반복문만 돌게 된다!

 두번째는, 문제에 나와있는 'N번째 감소하는 수가 없으면 -1을 출력한다.' 이다. 처음에는 무슨소리이지?? 라는 생각이 들었다. 그러나 생각해보니 9876543210 이후에는

 감소하는 수가 절대 나올 수 없다! 결국은 그 이후에는 무조건 -1 출력하면 된다.

3. Pain Point

 반복문의 횟수를 최소화하는 것에서 가장 많은 시간을 소요했다. 정답률이 낮은 이유가 있었다. 

 오늘은 문제를 풀면서 기분이 좋았다! 내가 노력한 것에 결실을 맺는 날이었으니까! 그리고 알고리즘을 꾸준히 풀어왔는데... 그 노력이 좋은 결과를 낼 수 있어서 좋았다!

 오늘은 기분이 좋은날이다! 암튼!