[프로그래머스] 줄 서는 방법 (Java)

프로그래머스 줄 서는 방법

문제풀이

다음 순열 함수(nextPermutation)을 구현해서 초기 배열에서 k번 실행하면 될 것 이라고 생각하고 해봤지만 시간초과가 나왔다. 최악의 경우 20!번의 함수 호출을 해야하기 때문이다.

그래서 특정 순열을 바로 구하는 방법을 생각해봤다. 예시로 주어진 [1, 2, 3]을 통해 손으로 쓰면서 규칙을 찾아보았다.

3명의 사람이 있을 때 5번째 순열을 구해보자.

• 첫 번째 자릿수에 1, 2, 3이 올 수 있는데 첫 번째 자릿수에 1이 올 수 있는 순열의 개수는 [1, 2, 3], [1, 3, 2] 두 가지다. 5번 째 순열을 구하는 것이니까 첫 번째 자릿수가 1일 때(2 가지) + 2일 때(2 가지)이므로 첫 번째 자릿수는 3임을 알 수 있다.
• 두 번째 자릿수에는 첫 번째 자릿수인 3을 제외한 1, 2가 올 수 있는데 두 번째 자릿수가 1인 경우 [3, 1, 2] 그리고 2인 경우 [3, 2, 1] 각 한 가지씩 가능하다. 그런데 순열에 따라서 1이 먼저 나올 것이고 이 경우가 5번째가 된다.

따라서 규칙은 다음과 같다.

• 첫 번째 자릿수부터 n번째 자릿수까지 하나씩 구해나갈 것이다. 자릿수에 각 숫자마다 (n - 자릿수)! 개수의 순열을 가진다.
• 개수가 k를 넘어서지 않는 최대의 개수까지 세고 그 때 숫자를 현재 자릿수에 넣는다.
• 다음 자릿수로 이동해서 동일하게 반복한다.

이 때 자릿수에 넣을 숫자는 사용하지 않은 가장 작은 수 부터 살펴봐야하므로 시작 전 숫자를 넣어둔 리스트를 오름차순 정렬한다.

구현코드

import java.util.*;

class Solution {    
    public int[] solution(int n, long k) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 1 ; i <= n ; ++i) list.add(i);
    
        return go(0, 0, n, k, new int[n], list);
    }
 
    private int[] go(long cnt, int idx, int n, long k, int[] answer, ArrayList<Integer> list){
        if(idx == n){
            return answer;
        }
        
        int num = 0;
        long add = fectorial(n - (idx + 1));
        Collections.sort(list);
        
        while(true){
            num = list.remove(0);
            if(cnt + add >= k) break;
            cnt += add;
            list.add(num);
        }
        
        answer[idx] = num;
        return go(cnt, idx + 1, n, k, answer, list);
    }
    
    private long fectorial(int n){
        long result = 1;
        while(n >= 1) result *= n--;
        
        return result;
    }
}