[Baekjoon] 백준 1038: 감소하는 수 - Java

문제

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

 

풀이

감소하는 수에서 몇번 째인지 구하는 문제이다. 접근 방식은 이러하다.

숫자를 1씩 감소하면서 자신의 숫자보다 작은 숫자들을 붙이고 재귀적인 호출을 해서 모든 감소하는 수를 리스트에 담고, N번째를 출력한다. 단, 리스트 크기보다 n + 1보다 작다면 그것은 존재하지 않는 것이다. 

9876543210을 생각해보면 int의 범위를 벗어나므로, long으로 해야한다.

 

필자는 이 문제에 대한 시간복잡도를 생각할때, 10!인 값으로 생각했고, 10!의 개수가 들어있는 리스트를 오름차순 정렬을 해야해서 1억 연산에 간신히 들어오겠네 라는 착각을 했다.

 

하지만, 리스트에 담기는 숫자들의 개수는 1023개이다. 

그 이유는 이러했다. 결국 감소하는 수를 생각해보면 숫자가 유일하다. 숫자가 중복이 되면, 그것은 감소하는 수가 아니기 때문이다. 

111(x)

321(o)

0~9까지 각 숫자가 선택이 되고 안되는 것에 대한 경우의 수를 생각해보면 2^10 => 1024개가 된다. 근데 1이 왜 빠졌을까?를 생각해보면 0~9까지의 모든 수들이 모두 선택이 되지 않았을 경우, 즉 수가 아무것도 없을 경우가 있기때문에, 1이 빼진 1023이 된다.

 

즉, 10개의 서로 다른 숫자들 중에서 선택되고 안되는 경우에 대한 모든 경우의 수(1024) - 10개의 서로 다른 숫자들이 모두 선택이 되지 않은 경우(1)을 빼서 1023이 된다.

 

이 문제의 시간복잡도는 1023 * log(1023)이다.

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    private static ArrayList<Long> list;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        //감소하는 수를 담은 리스트
        list = new ArrayList<>();
        
        backTrack("", 9, 0);
        
        if (list.size() < n + 1) {
            System.out.print(-1);
            return;
        }
        
        //오름차순 정렬
        Collections.sort(list);
        
        //출력
        System.out.print(list.get(n));
        
        br.close();
    }
    
    private static void backTrack(String s, int idx, int depth) {
    	//모든 수를 다 사용했을 경우,
        if (depth > 10) {
            return;
        }
        
        //빈 문자열 고려
        if (!s.isEmpty()) {
            list.add(Long.parseLong(s));
        }
        
        for (int i = idx; i >= 0; i--) {
            backTrack(s + i, i - 1, depth + 1);
        }
    }
}