programmers.co.kr/learn/courses/30/lessons/12936
[풀이]
3명의 사람이 줄을 서는 방법을 사전 순으로 나열해보자.
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
총 방법은 6가지이다. (3!)
그럼 이제 첫 번째에 사람을 세우는 경우만 보면,
1
1
2
2
3
3
첫 번째에 1이라는 사람이 나오게 되는 경우의 수는 2가지다.
마찬가지로 2, 3이라는 사람이 나오게 되는 경우의 수도 2가지 씩이다.
첫 번째 줄에 사람을 세우는 경우를 그림으로 그리면, 구하고자 하는 K번째를 경우를 찾기 위해서는 첫 번째에 어떤 사람이 나와야 하는지 알 수 있다.
줄 서는 방법 중 5번 째 방법을 구하고 싶다. 5번 째 방법은 무조건 첫 번째 사람으로 3을 세워야만 한다.
[3, 1, 2]
[3, 2, 1]
이런 식으로 i번째 사람을 세우는 모든 경우들 중 K번째 방법을 포함하는 경우를 찾아서 하나씩 answer[] 배열에 추가하면 된다.
두 번째 줄에 사람을 세우는 경우
두 번째는 이제 [3, ] 으로 시작하는 경우들만 보면 된다.
예제에서는 N = 3 이기때문에 바로 답을 여기서 구할 수 있다.
답 : [3, 1, 2]
(두 번째에서 1을 고르면 그 뒤엔 2가 나오는 경우밖에 없기 때문에)
그럼, N = 5 이면 어떻게 시작을 해야하나
사람의 수가 N인 경우, 줄을 세우는 모든 경우의 수는 N! 이다. (N * (N-1) * ... * 1)
N = 5이면, 모든 경우의 수는 120이다.
모든 경우의 수를 5로 나누면 각각 24가지의 하위 경우의 수를 갖게 된다.
만약, 내가 구하고자 하는 K = 95 라면,
95번 째 줄 서는 방법은 첫 번째 사람이 무조건 4가 나와야만 하는 것이다.
그 다음은 이제 동일한 방법으로 모든 경우의 수를 남은 사람의 수로 나누고, K번째 경우가 속하는 사람을 또 찾으면 된다.
남은 인원 : 4명
모든 경우의 수 : 24 가지
각각 가지게 되는 하위 경우의 수 : 6가지
여기서 95번 째 경우를 포함하는 '5'를 선택하고, 또 반복하면 된다..
class Solution {
public int[] solution(int n, long k) {
int[] answer = new int[n];
boolean[] chk=new boolean[n+1];
int cnt=n;
long total=1;
for(int i=1;i<=n;i++){
total*=i;
}
long start = 1;
for(int idx=0;idx<n;idx++){
long div=total/cnt;
int tn=-1;
long ts=start;
for(int i=1;i<n+1;i++){
if(chk[i]){
continue;
}
if(start<=k){
tn=i;
ts=start;
start+=div;
}else{
break;
}
}
answer[idx]=tn;
chk[tn]=true;
start=ts;
total=div;
cnt-=1;
}
return answer;
}
}