문제 탐색하기

입력 자료 정리

1. n은 찾고자 하는 줄어드는 수의 번호로 리스트의 찾고자하는 인덱스값이 될것이다

해결방법 추론

1. 놀랍게도 백트래킹으로 가능하다 최대 가능수가 9876543210이기 때문이다
2. 줄어드는 수를 구하기 위해 0~9의 수를 각 원소로 두고, 선택하냐 안하냐로
   수를 만들어 나가면 될 것이라 생각한다
3. 대신 줄어드는 수를 만들기 위해 9876543210으로 역순으로 원소를 둬야 한다
4. 백트래킹 탐색을 설계하여, 가능한 모든 줄어드는 수를 구한 뒤,
   중복 안 되게 리스트에 넣어 보관하고 입력값 k번째의 값을 출력한다면
   문제를 해결할 수 있을 것이다

시간복잡도 계산

1. 시간복잡도는 어떻게 될까? 먼저 10개의 원소를 선택하냐 안하냐이기 때문에
   백트래킹에서 2^10만큼 발생할 것이다.
2. 이어서 k번째 원소를 선택하므로 O(1)만큼의 연산이 발생할 것이다
3. 따라서 시간복잡도는 O(2^10)이 되며 시간제한에 걸리지 않고 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리하기

1. 먼저 k는 변수로 관리해준다
2. 이어서 입력값 이외의 탐색 원소인 9876543210은 int형 배열로 담아서 관리한다
3. 그리고 백트래킹 결과를 담아줄 리스트를 하나 만들어 관리한다

백트래킹 설계

함수식

- backtracking(int now, int depth)
1. 원소의 선택으로 현재까지 완성된 값을 가지고 있는 now 파라미터와
base condition을 위한 depth를 파라미터로 가지고 있다
2. 매 탐색마다 최우선으로 list에 now값을 가지고 있는지 파악하며, 없으면 list에 넣는다

재귀식

- backtracking(10 x now + arr[depth], depth+1)
- backtracking(now, depth+1)
1. 선택하는 경우와 선택하지 않는 경우로 나눠서 재귀식을 돌려준다
2. 줄어드는 수로 만들기 위해 현재수를 왼쪽으로 밀도록 10을 곱해주고
arr[depth]의 원소 값을 더해준다
3. 선택하지 않는 경우는 그대로 now를 넘겨주며 depth는 진행을 위해 +1을 해준다

base condition

- if(depth == 10){return;}
1. depth가 10이면 배열의 인덱스 범위를 벗어나므로 종료해준다

출력값 설계

1. 리스트를 오름차순 정렬을 해주고, k가 리스트 크기보다 크면 -1을 출력한다
2. 만약 작거나 같다면 list의 k-1번째 인덱스의 값을 출력하면 정답이 될텐데...

시도회차 수정

1회차 시도 실패

1. 31%에서 틀려버렸다. 로직은 맞는데 뭐가 원인일까 다시 살펴보던중..

원인분석

1. 리스트에 들어갈 숫자의 크기가 int형 타입의 범위를 벗어날 수 있다는 것을 알게 되었다
2. 따라서 리스트의 타입과 백트래킹 now 파라미터를 long타입으로 바꿔주었다

2회차 시도 성공

1. 타입을 바꾸고 다시 제출했을 때 바로 성공하였다!

정답 코드

(1회차 시도 성공)

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


public class Main {

    static int[] arr = {9,8,7,6,5,4,3,2,1,0};
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int k = Integer.parseInt(br.readLine());
        backtracking(0,0);

        Collections.sort(list);
        if(list.size() < k){
            bw.write("-1");
        }else{
            bw.write(list.get(k-1)+"");
        }

        br.close();
        bw.close();
    }

    private static void backtracking(int now, int depth) {
        if(!list.contains(now)){
            list.add(now);
        }

        if(depth == 10){
            return;
        }

        backtracking(10*now + arr[depth], depth+1);
        backtracking(now, depth+1);
    }
}

(2회차 시도 성공)

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


public class Main {

    static int[] arr = {9,8,7,6,5,4,3,2,1,0};
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int k = Integer.parseInt(br.readLine());
        backtracking(0,0);

        Collections.sort(list);
        if(list.size() < k){
            bw.write("-1");
        }else{
            bw.write(list.get(k-1)+"");
        }

        br.close();
        bw.close();
    }

    private static void backtracking(int now, int depth) {
        if(!list.contains(now)){
            list.add(now);
        }

        if(depth == 10){
            return;
        }

        backtracking(10*now + arr[depth], depth+1);
        backtracking(now, depth+1);
    }
}

문제 링크

1174번 - 줄어드는 수