[백준] 1038 감소하는수

문제보기

똥꼬집 발동해서 수열로 하루종일 풀었던 문제..

import java.util.*;
import java.io.*;
public class Main{
  // 다음 순열을 만들어주는 함수
  public static boolean next_perm(int[] arr){
    int i = arr.length -1; 
    while( i > 0 && arr[i-1] >= arr[i]){
      i--;
    }
    if(i <= 0){
      return false; 
    }
    int j = arr.length -1; 
    while( arr[j] <= arr[i-1] ){
      j--;
    }

    int temp = arr[j];
    arr[j] = arr[i-1];
    arr[i-1] = temp;

    int k = arr.length -1;
    while( i < k ){
      temp = arr[k];
      arr[k] = arr[i];
      arr[i] = temp;
      i++;
      k--;
    }
    return true; 
  }

  public static void main(String []args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    // 최대 10자리 숫자를 사용한 예(9876543210) 가 1022번째 이므로 
    // 1023번째 이상의 감소하는 수는 존재하지 않는다 
    if(n >= 1023){
      System.out.println(-1);
      return;
    }
    // 한자리 수는 그 자체로 감소하는 수
    if( n < 10 ){
      System.out.println(n);
      return;
    }
    // 결국 감소하는 수라는건, 10개의 숫자 중 임의로 몇개만 선택하면
    // 자동으로 감소하는 방향으로 배열된다고 생각하면 된다.
    // 따라서 차례대로 10C0, 10C1, 10C2 ... , 10C10 을 쭉 누적합 해둔 수열이 필요하다.
    int[] c = {0, 9, 54, 174, 384, 636, 846, 966, 1011, 1021, 1022};
    // l에는 입력받는 n이 c에서 속하는 구간(인덱스) 를 저장할 변수다
    int l = -1;
    for(int i = 1 ; i < c.length ; i++ ){
      if(n <= c[i]){
        l = i; // 처음으로 자기보다 큰 원소를 만났을때 빠져나온다. 예 : 18입력시 i = 2일때 빠져나옴
        break;
      }
    }
    // l은 즉 숫자의 자릿수를 의미한다.
    // 위의 예로 계속해보면, l=2이므로 18번째 감소수는 두자리 숫자다.
    
    // idx에는 18번째 감소수가 두자리 숫자 그룹내에서 몇번째에 속하는지를 저장한다.
    int idx = n - c[l-1];
    
    // num은 선택될 숫자를 1과 0으로 표시할 배열
    int[] num = new int[10];
    
    // l이 2일 때에는 0000000011로 초기화 되어야 한다
    for(int i = 9 ; i >= 10-l ; i--){
      num[i] = 1;
    }
    int cnt = 1;
    // 이제 본격적으로 순열을 돌려가며 해당 위치를 찾는다.
    do{
      if( cnt == idx ){
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < 10 ; i++ ){
          if(num[i] == 1){
            sb.append(9-i); // num에서 0번째 원소는 9의 유무를 나타내므로 이렇게 바꿔줘야함
          }
        }
        System.out.println(sb);
        break;
      }
      cnt++;
    }while(next_perm(num));
  }
}