[ Baekjoon - 10/07 ] - 1038번: 감소하는 수

• 문제 링크 : https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

 

• 소요 시간 : 1시간

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 512MB
   • 문제
     • 입력값 N(0≤N≤1,000,000)
   • 이해
     • 모든 자릿수가 기준으로 앞의 수보다 뒤의 수가 다 작다면 감소하는 수라고 정의한다.
     • 이때 N번째 감소하는 수를 구하라는 문제이다. 문제 이해는 어렵지 않아보이지만, 감소하는 수가 제한이 생길수 밖에 없다는 것 정도는 분석해야할듯싶다. 한자리수기준으로 비교하니까 전체자릿수는 10자리 뿐일 것이다. 9876543210으로.
     • 여기까지 이해했다면 문제는 어떻게 구현하느냐 이겠지..
2. 문제를 익숙한 용어로 재정의와 추상화
   • 이해를 위한 과정이므로 생략한다.
3. 문제를 어떻게 해결할 것인가

   • 

   • 우선 자릿수기준으로 어떤식으로 값이 나오는지 알기위해 1~3자리 정도 써보았다.
   • 한자리 수의 경우, 문제에서 0은 아니고 1,2는 맞다 했으므로 1부터 9까지는 다 가능하다.
   • 두자리 수의 경우, 앞자리가 0인경우는 불가능하고 1부터 가능하다.
     앞자리가 1이면 뒤에는 무조건 0, 앞자리가 2이면 뒤에는 1 또는 0, 앞자리가 3이면 뒤에는 2 또는 1 또는 0 ...
     즉, 전 케이스에서의 재귀로 접근이 가능할거라 생각했다. 일단 확실하지 않아서 좀더 써보기로 했다.
   • 세자리 수의 경우, 앞자리가 2여야 뒤에 1과0이 오므로 가능하다.
     앞자리가 3이면 뒤에는 21,20,10이 가능하다. 이런식으로 쭉쭉 써보면 두자리수일때의 재귀스러운(?) 구성임을 확인할 수 있다.
   • 1st 접근 - 재귀)
     • 앞의 자릿수때문에 뒷자리수가 결정되는 형태이므로 재귀적으로 구해질 수 있을거라 생각했다.
     • 앞자리를 반복문으로 돌려서 첫자리를 0~9로 넣어두고 함수를 호출한 뒤, 뒷자리수는 앞자리-1부터 올 수 있으므로  반복문으로 돌려 뒷자리에 못올때까지 재귀호출을 하며 리스트에 숫자값을 넣는 방식으로 구현하면 될것 같았다! 후에 정렬 한번이면 순서대로 위치될테니.
     • 결과적으로는 Integer가 아닌 Long을 사용해야한다는 점, 인덱스 에러가 날 수 있다는 자잘한 오류를 잡고나니 코드가 성공적으로 구현되었다.
   • 2nd 접근 - 조합)
     • 사실 자바로 조합구현하기 싫어서(라이브러리 내놔아ㅠ) 자바는 재귀를 이용해 접근하고자했고... 파이썬으로 조합을 구현해보자는 생각을 먼저했다.
     • 파이썬의 itertools는 조합을 도출할때 케이스 하나하나를 출력해주므로 이를 이용하려했다.
     • 한참을 생각하다가.. 자릿수별로 호출하여서 원하는 순서로 정렬해버리면 될듯 싶었다.
     • 파이썬의 조합은 오름차순식으로 값을 도출하므로 위 순서를 바꿔버리면 전에 실행했던 숫자와 중복없이 새로운 숫자를 뽑아낼 수 있다!
     • 이를 이용해 값(한자리 숫자 묶음)을 뽑고 이를 숫자 하나로 결합하여 리스트에 append를 한다면 실제 증가하는 수가 구해질 테고, 정렬까지 한다면 차례대로 구해질수 있을거라 생각했다. 
4. 위 계획을 검증
   • 말로 설명하기가 좀 난해했지만.. 위에 3번과정과 밑 코드를 보면 이해될거라 생각한다.
     결국 재귀나, 조합이나 다 앞자리로 인해 뒷자리가 결정된다는 점을 이용했고, 재귀로 가능한 숫자를 붙여서 리스트에 더하든, 조합으로 숫자를 호출하고 조금의 조작으로 더하든 결과적으로 같은 흐름이다.
5. 계획 수행 (실제코드 작성) 
   1. Java 11 (재귀 이용)

      1. import java.io.*;
         import java.util.*;
         
         public class Main {
             public static int N;
             public static List<Long> increasedList;
         
             public static void main(String[] args) throws NumberFormatException, IOException {
                 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
                 try {
                     N = Integer.parseInt(br.readLine());
                     increasedList = new ArrayList<Long>();
                     for (int i = 0; i < 10; ++i) {
                         numMaker(i, 1);
                     }
         
                     Collections.sort(increasedList);
                     System.out.println(increasedList.get(N));
                     
                 // 인덱스 에러라는 것은 최댓값인 9876543210을 초과했다는 것
                 }catch (IndexOutOfBoundsException e){ 
                     System.out.println(-1);
                 }
             }
         
             public static void numMaker(long num, int len) {
                 if (len > 10) {
                     return;
                 }
         
                 increasedList.add(num);
                 for (int i = 0; i < 10; ++i) {
                     if (num % 10 > i) {
                         numMaker((num * 10) + i, len + 1);
                     }
                 }
             }
         }

   2. Python 3 (조합 이용)

      • from itertools import combinations
        
        N = int(input())
        ans = []
        
        dataset = [i for i in range(10)]
        for i in range(1, 11):
            # 해당 자릿수 만큼 조합을 생성
            comb_list = list(map(list, combinations(dataset, i)))
        
            # 조합을 뽑으면 뒤로갈수록 커지는 식으로 생성되므로, 반대로 정렬하면 큰수가 앞에오도록 뽑을 수 있다 
            for j in range(len(comb_list)):
                comb_list[j] = sorted(comb_list[j], reverse=True)
        
            # 뽑은 숫자 한자리 들을 모아서 한 숫자로 만든뒤 append 연산 ex) [1,2,3,4] -> 1234
            for j in range(len(comb_list)):
                ans.append(int(''.join(map(str, comb_list[j]))))
        
        # 정렬해야 커지는 순서대로 위치를 잡을 수 있으므로, 인덱스만으로 증가하는 수를 뽑을 수 있다.
        ans.sort()
        print(-1 if N >= len(ans) else ans[N])

      • # 개선해본 코드
        import sys
        from itertools import combinations
        
        input = sys.stdin.readline
        
        n = int(input())
        string = "9876543210"
        
        string_comb = []
        for i in range(1, 11):
            for comb in combinations(string, i):
                string_comb.append(int(''.join(list(comb))))
        
        string_comb.sort()
        
        if n >= len(string_comb):
            print(-1)
        else:
            print(string_comb[n])

 

• 결과