[ JAVA ] 프로그래머스 - 줄 서는 방법

https://programmers.co.kr/learn/courses/30/lessons/12936

코딩테스트 연습 - 줄 서는 방법

 

[  풀이  ]

처음에는 단순히 백트래킹을 이용해 줄을 설 수 있는 모든 경우의 수( 순열 ) 을 구해서 list 에 저장한 뒤, 사전 순으로 정렬하여 k 번째에 저장된 줄을 서는 방법을 추출해 답을 내었다. 하지만 시간초과가 발생하였다. 모든 경우의 수를 찾는 방법이 아닌 주어진 k 와 n 이라는 단서만으로 답을 구해야 하는 문제라고 생각하였다.

 

1. 먼저 1번 부터 n번까지의 숫자( 사람 번호 )를 ArrayList에 추가한다. 이 리스트는 줄에 설 사람들의 후보들이다.

 

2. 1부터 n까지의 곱 n! 를 구한다 ( div )

 

3. k 에 ( div / n ) 를 나눈다 ( idx )

 

4. 리스트에서 idx번째 사람을 뽑아서 맨 앞줄에 세운다. 그리고 뽑은 사람을 리스트에서 제거한다.

 

5. 위의 2 ~ 4 번 과정을 사람 수 만큼 반복한다. 이때 반복할 때마다 k의 값은 div 로 나눈 나머지가 된다. 그리고 div는 ( n - i ) 만큼 나눈 값이 된다.

 

[ 전체 코드 ]

import java.util.*;
class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[ n ];
        List<Integer> nums = new ArrayList<>();
        k = k - 1 ;
        int idx;
        long div = 1;
        for( int i = 1 ; i <= n ; i++ ){
            nums.add( i );
            div *= i;
        }        
        for( int i = 0 ; i < n ; i++ ){
            div /= ( n - i ) ;
            idx = (int)( k / div ) ;
            answer[i] = nums.get(idx);
            nums.remove(idx);    
            k = k % div ;            
        }
        return answer;
    }
}