현재까지 풀었던 문제 중 가장 이해가 어려웠던 문제인것 같습니다.
확률과 통계에 대한 개념이 있으신 분들은 쉽다곤 하네요..
[ 풀이 ]
순열을 이용하는 문제입니다.
n이 3이면 3!의 경우의 수만 구하면되지만, 최대값인 20!의 값을 구해야 한다면 모든 경우의 수를 살펴볼 수 없습ㄴ디ㅏ.
따라서 k번째의 순열만 빠르게 구할 수 있는 방법을 찾아봐야합니다.
문제 예시를 먼저 보겠습니다.
- [1, 2, 3]
- [1, 3, 2]
- [2, 1, 3]
- [2, 3, 1]
- [3, 1, 2]
- [3, 2, 1]
n은 3인데 앞자리의 숫자는 2개를 기준으로 변경된다는 것을 알 수 있습니다.
만약 앞자리가 고정되어 있다면 나머지 2개의 숫자들만 사용해서 순열을 구하면 됩니다.
그래서 앞자리 교체주기를 생각해봅시다.
[ 1 ~~ ]
[ 2~~ ]
이렇게 앞자리가 바뀌는 교체주기는 (n-1)! 가 되는것을 알 수 있습니다.
그리고 k는 모든 순열에서 k번째 위치한 순열을 의미합니다.
그래서 만약 k가 5라면
arr [ index / (n-1)! ] 을 하게 되면 현재 주기에서 맨 앞에 위치한 숫자입니다.
여기서 k는 순번을 의미하므로 저희가 필요한 인덱스를 찾으려면 인덱스는 0부터 시작하므로 1을 빼줘야합니다.
따라서 초기 인덱스 값은 k-1로 잡아주면 됩니다.
즉, arr [ k-1 / (n-1)! ] 를 해주면 현재 주기에서의 맨 앞에 위치한 숫자의 인덱스가 됩니다.
예를 들어,
n = 5, k = 110 일 때를 예를 들어 보겠습니다.
- 모든 경우의 수 : 5!
- 맨 앞자리 교체주기 : 4!
- 맨 앞자리 숫자의 인덱스 : 109 / 4!
이제 맨 앞자리를 구했으니 다음 숫자를 구해봅시다.
그러면 맨 앞자리 하나의 숫자를 고정 해줬으므로 다음과 같이 그 다음 숫자를 구할 수 있습니다.
이를 위해선 두가지 작업이 추가적으로 더 구현됩니다.
1) 인덱스 값을 다음 순열을 위해 재조정
2) 사용한 배열 원소를 제거
인덱스 값은 현재 주기에서 가장 앞자리의 숫자를 찾아주는 역할을 합니다.
그래서 앞자리 숫자의 인덱스를 찾고 난 후 다음 순열에서도 맨 앞자리를 찾을 수 있도록 k 값을 재조정해줘야 합니다.
(k-1) % (n-1)! 해주면 됩니다.
이렇게하면 자연스레 (n-1)! 를 넘을 수 없고, 다음 경우의 수에서 맨 앞자리 숫자를 가리키는 인덱스를 동일한 로직으로 찾을 수 있습니다.
이때, 만약 k의 값이 0이 되면 정확하게 나눠떨어졌다는 소리이므로 반복문이 종료됩니다.
n = 4, k = 5 라고 예를 들어봅니다.
[ 1,2,3,4 ]
[ 1,2,4,3 ]
[ 1,3,2,4 ]
[ 1,3,4,2 ]
[ 1,4,2,3 ]
[ 1,4,3,2 ]
[ 2,1,3,4 ]
첫 번째 자리 수가 특정 수가 되는 경우 : (n-1)! 단위로 끊어짐
( 단, 앞이 1인 배열은 0번의 위치에 해당됩니다.
ex. [ 1,2,3,4 ] , [1,~~~] : 0
[ 2,3,4,1 ] , [2,~~~] : 1... )
그래서 해당하는 위치를 구하려면
k / (n-1)! : 배열의 순서의 번호
k % (n-1)! : 배열 순서 내부 번호
import java.util.ArrayList;
public class skillCheck2 {
/**
- 문제 해석
> 일렬로 줄 서 있음
> 1~n 까지 번호가 매겨져 있음
> n명의 사람이 줄 서는 방법은 여러가지 있음
> 사람의 수 n, 자연수 k가 주어질 때, 사람을 나열하는 방법을 사전순으로 정렬
> k번째 정렬된 수의 배열을 리턴
**/
public static void main(String[] args) {
}
public int[] solution(int n, long k) {
int[] answer = new int[n];
ArrayList<Integer> list = new ArrayList<>();
int fn = 1;
for (int i = 1; i <= n; i++) {
fn *= i; // fac 구하기
list.add(i);
}
k--;
int idx = 0;
while (idx < n) {
fn /= n - idx;
answer[idx++] = list.remove((int) (k / fn));
k %= fn;
}
return answer;
}
}
* 참조했던 블로그입니다.
https://gogoma.tistory.com/150