[구현] 프로그래머스 줄 서는 방법 (실패 분석 - 아이디어)

접근

https://github.com/search?q=dla6703

이 문제는 처음에 dfs로 풀었다가 시간초과가 발생하여
중간에 조금이라고 줄여보려고 노력하였습니다.

그러나 애초에 dfs로 접근해서는 안되는 문제였습니다.

• 처음 시도 : 단순히 dfs와 백트랙킹
• 두 번째 시도
  처음 시작하는 수를 구해서 모두 돌지 안도록한다.

   long total=1;
         
   //한 개당 갖는 경우의 수
   for(int i=1;i<n;i++) total*=i;
         
         
   //시작하는 수
   int start_num =(int)((k-1)/total)+1;
   // 결국 구해야하는 k번째
   int last_k = (int)(k%total)==0? (int)(total) :(int)(k%total);

  그러나 여기서 문제가 있습니다.
  20!이라고 가정할 때
  하나의 숫자 당 가지는 경우의 수는
  121645100408832000
  최악의 경우 121645100408832000번의 비교가 비교합니다. 따라서 dfs로 풀어서는 안되는 문제라는 것을 깨달았습니다.
  
• 세 번째 시도
  다른 분의 풀이를 보고 풀었습니다.

하나의 숫자가 가지는 경우의 수가 있을 때
k가 몇 번째의 숫자를 가지게 되는지
그리고 이 k가 하나의 숫자를 선택했을 때 얼만큼 줄어들게 되는지를 생각하면 됩니다.

가장 핵심은 하나의 숫자가 몇 개의 경우의 수를 가지는지!
이 부분입니다.

풀이

import java.util.*;

class Solution {
    public int[] solution(int n, long k) {
        int[] answer= new int[n];
        ArrayList<Integer> list = new ArrayList<>();
        
        long total=1;
        
        for(int i=1;i<=n;i++){
            list.add(i);
            total*=i;
        }
        
     
        k--;
        int idx=0;
        for(int i=0;i<n;i++){
              
           //개당
            total=total/(n-i);
            
            //시작하는 수들을 차례로 넣어준다.
            answer[i]=list.remove((int)(k/total));
            // 구한 수의 경우의 수까지 빼기
            k = k%total;
        }     
        return answer;
    }    

}