[Programmers] 줄 서는 방법 (Java)

문제링크

문제 설명

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러 가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열했을 때, k번째 방법을 return 하는 solution 함수를 완성해 주세요.

 

제한사항

• n은 20 이하의 자연수입니다.
• k는 n! 이하의 자연수입니다.

입출력 예

n	k	result
3	5	[3,1,2]

 

문제 풀이

처음 문제를 풀 때에는, 규칙에 따라 모든 순열조합을 만들면서, k 번째의 순열을 반환하도록 하려고 했다. 하지만 순열의 경우의 수는, n! 이므로, 최악의 경우에 시간복잡도가 n! 이므로, 시간제한에 걸릴 것 같았다. 따라서 규칙을 찾아보기 위해, n = 4 일 때 모든 조합을 사전 순으로 나열해 보았다.

1234	2134	3124	4123
1243	2143	3142	4132
1324	2314	3214	4213
1342	2341	3241	4231
1423	2413	3412	4312
1432	2431	3421	4321

위와 같이 나열해 보니, 오른쪽에서 부터 n번째 자릿수는 다음과 같은 규칙에 의해 정해진다는 사실을 알게 되었다.

set = {1, 2, 3, 4} 일 때,
k = k - 1
n 번 째 자릿수 = set.get(k / (n - 1)!)
k = k % (n - 1)!
n -= 1
set.remove()

 

예를 들어, k = 10, 원하는 순열이 [2, 3, 4, 1] 일 때, 

 

set = {1, 2, 3, 4}
첫 번째 반복
set.get(9 / (4 - 1)!) => set.get(9 / 6) => set.get(1) => 2
k = 9 % 6 => 3
n -= 1
set.remove(1)

두 번째 반복
set = {1, 3, 4}
set.get(3 / 2) => set.get(1) => 3
...

세 번째 반복
set = {1, 4}
set.get(1 / 1) => set.get(1) => 4
...
네 번째 반복
set = {1}
set.get(0 / 1) => set.get(0) => 1

 

위에서 get 한 부분들을 모아보면, 원하는 순열인 {2, 3, 4, 1} 이 된다.

 

코드

Java

import java.util.*;

class Solution {
    public int[] solution(int n, long k) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) list.add(i);
        int[] answer = new int[n];
        fact(n);
        k -= 1;
        int d = n - 1;
        for (int i = 0; i < n; i++) {
            long temp = fact(d--);
            int index = (int) (k / temp);
            answer[i] = list.get(index);
            list.remove(index);
            k %= temp;
        }
        
        return answer;
    }
    
    private long fact(int n) {
        if (n <= 1) return 1;
        return (long) n * fact(n - 1);
    }
}

 

여담

Java 풀이가 처음에는 효율성 테스트에서 실패했었다. 그 이유는 List를 초기에 생성과 동시에 선언하는 방식 (아래와 같은 방식)으로 생성해 주었는데, 해당 방식 비효율적이었나 보다. 위와 같이 변경해 주니 해결되었다.

//효율성 테스트에서 실패했던 생성방식
List<Integer> list = new ArrayList<>() {{
	for (int i = 1; i <= n; i++) add(i);
}}