[백준] 1174 - 줄어드는 수(Java)

문제 파악

https://www.acmicpc.net/problem/1174

풀이

조합보다는 BFS(Queue)를 사용하여 구현하면 더 쉽고 간단하게 풀이할 수 있다.

큐에 적재하는 숫자는 다음과 같다.

0	-	-	-
1	10	-	-
2	20	-	-
	21	210	-
3	30	-	-
	31	310	-
	32	320	-
		321	3210
...
9	90	-	-
	91	910	-
	92	920	-
		921	9210

1열(0,1,2,3...,9), 2열(10,20,21,30...98), 3열(210,310,...987), ... 순서대로 큐에 적재된다.

poll 한 원소의 끝 자리(poll%10)보다 작은 숫자를 붙여 다시 큐에 적재해준다.
예를 들어 만약 93이 최신 숫자였다면, 다음 뎁스의 감소하는 숫자는 [930, 931, 932]이 되겠다.

또한 FIFO로 순서가 보장되기 때문에 큐에 넣을 때 작은 숫자부터 넣어주면 추가 정렬은 필요 없다.

조심할 부분은 큐의 원소가 상당히 커지므로, 자료형에도 신경을 써 주도록 하자 😊

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = Integer.parseInt(new Scanner(System.in).nextLine());
        Queue<Long> queue = new LinkedList<>();
        for (long i = 0; i <= 9; i++) {
            queue.offer(i);
        }
        long localN = 1;
        while (!queue.isEmpty()) {
            long poll = queue.poll();
            if (localN == n) {
                System.out.println(poll);
                return;
            }
            localN++;
            for (int i = 0; i < poll % 10; i++) {
                queue.offer(poll * 10 + i);
            }
        }
        System.out.println(-1);
    }
}