[백준 1038번] 감소하는 수 - JAVA

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

1038번: 감소하는 수

풀이

사용한 알고리즘 : 큐

 

풀이전략

1. 0~9의 수를 큐와 리스트에 추가한다.

2. 큐의 원소를 하나씩 deQueue하고 그 수보다 작은 수를 찾은 뒤

    '(deQueue한 원소)x10 + (원래 원소보다 작은 찾은 수)'를 리스트에 추가한다.

    이를 큐가 빌 때까지 반복한다.

3. 리스트의 N번째 값을 출력한다.

 

제출코드

import java.util.Main*;

public class Problem1038 {

    static List<Long> list = new ArrayList<>();
    static ArrayList<Long> q = new ArrayList<>();

    static void func(int N){
        Queue<Long> tempQ=new LinkedList<>();
        for(long i=0;i<10;++i){
            tempQ.offer(i);
            q.add(i);
        }

        while(!tempQ.isEmpty()){
            long a=tempQ.poll();
            long x=a%10;
            for(int i=0;i<x;++i){
                long num=a*10+i;
                tempQ.offer(num);
                q.add(num);
            }
        }

        if(N>=q.size()) System.out.println(-1);
        else System.out.println(q.get(N));
    }

    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        func(N);
    }
}