> 문제
문제 : [줄 서는 방법]
> 문제풀이
문제에서 k번째의 숫자를 찾아야 한다.
k는 n! 이하의 자연수이기 때문에 recursive하게 풀지는 못한다.
아이디어는 1 2 3 4 5 의 숫자가 있을 때,
'’뒤에서부터 자리를 바꾸면 되지 않을까” 에서 착안하였다.
k번 바꿀 수 있다면 뒤에서 부터 바꿔주면 된다.
1이 맨 앞에올 수 있는 경우의 수는 4! 이다.
첫 번째 인덱스는 k/4!이 될것이다.
두 번째 인덱스는 첫번째 인덱스 나머지 값 k%4! 에서 3!을 나눈 값이다.
즉, 해당 인덱스에 올 수 있는 값은
k/(n-1)!이며,k=k%(n-1)!해주어야 한다.소스는 다음과 같다.
주의할 점은 아래 소스에서 List를 사용했는데 LinkedList로는 통과할 수 없다.
LinkedList는 탐색시간이 O(n) 이며 통과하지 못하였다.
ArrayLiset의 탐색시간이 O(1)이므로 통과할 수 있다.
import java.util.*;
class Solution {
public int[] solution(int n, long k) {
int[] answer = new int[n];
long[] fact = new long[n+1];
fact[0] = 1;
for(int i=1; i<n+1; i++){
fact[i]=i*fact[i-1];
}
List<Integer> list = new ArrayList<>();
for(int i=0; i<n; i++){
list.add(i+1);
}
k--;
for(int i=0; i<n; i++){
int index = (int)(k/fact[n-i-1]);
answer[i] = list.remove(index);
k = k % fact[n-i-1];
}
return answer;
}
}
문제 출처 : Programmers