#백준_1038 괄호 - Java 자바

#유형 : 브루트포스, 큐

#난이도 : 골드5

# 큐를 사용하면 생각보다 편하게 접근할 수 있던 문제

# 큐에 1~9를 미리 넣어놓고 헤드부터 poll하면서 num % 10 한 만큼 반복문을 돌려 더하면 된다.

아래의 로직을 잘 생각하면 해결할 수 있다.

# 주의해야할 점은 int 형으로 하면 범위문제로 long으로 접근

for(int i=0; i<num%10; i++)

{

     Arr[idx] = num * 10 + i;

}

Ex) 1 -> 1*10 + 0 = 10

Ex) 2 -> 2*10 + 0 = 20

Ex) 2 -> 2*10 + 1 = 21 

. . . 

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1038 {    
    static int idx = 9;
    static int N;
    static Queue<Long> queue = new LinkedList<Long>();
    static long arr[] = new long[1000001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for(int i=1; i<10; i++) {
            queue.add((long) i);
            arr[i] = i;
        }
        
        solve();
        if(N!=0 && arr[N] == 0) {
            System.out.println("-1");
        }else {
            System.out.println(arr[N]);
        }
    }
    
    public static void solve() {
        while(idx <= N) {
            if(queue.isEmpty()) {
                return;
            }
            
            long num = queue.poll();
            long lastNum = num % 10;
            
            for(int i=0; i<lastNum; i++) {
                queue.add((num * 10) + i);
                arr[++idx] =(num * 10) + i;
            }
        }
    }
}