문제
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] |
풀이
순열을 이용하는 문제다. 입출력 예시에서 n이 3이기 때문에 3명이 줄을 설 수 있는 모든 경우의 수는 3P3 = 3!, 즉 팩토리얼과 같다. 하지만 문제에서 주어진 n의 최댓값은 20이고 20!의 값은 2432902008176640000이라는 매우 큰 수이다. 따라서 모든 순열을 구해 k번째 위치의 방법을 리턴하는 것은 당연히 시간복잡도를 통과할 수 없다.
따라서 k 번째의 순열만 빠르게 구할 수 있는 방법을 생각해보아야 한다. 문제 예시와 같이 [1, 2, 3] 이 있을 때의 경우로 찬찬히 살펴보자. 먼저 위와 같이 주어져있다면 다음과 같이 줄을 세울 수 있다.
- [1, 2, 3]
- [1, 3, 2]
- [2, 1, 3]
- [2, 3, 1]
- [3, 1, 2]
- [3, 2, 1]
여기서 첫번째-두번째는 맨 앞자리가 1, 세번째-네번째는 맨 앞자리가 2, 다섯번째-여섯번째는 맨 앞자리가 3인 것을 알 수 있다. 위의 예시에서 주어진 n은 3인데 2개를 기준으로 앞자리의 숫자가 변경되는 것을 알 수 있다. 왜 2개를 기준으로 앞자리가 변화하는 것일까? 만약 앞자리가 고정되어 있다면 남은 2개의 숫자들의 순열만 필요할 것이다. 이때 남은 2개의 숫자의 2!이 2이기 때문에 2개의 주기를 갖게된다. 만약 n이 4 였다면 3!이 앞자리 숫자 교체 주기가 되었을 것이다.
따라서 위의 과정을 통해 우리는 처음 시작하는 숫자를 인덱스 값으로 구할 수 있다. 위에서 k가 5이기 때문에 우리는 5-6번째 순열이 항상 3으로 시작한다는 것을 알고 있다. 이는 위에서 보인바와 같이 arr[인덱스 / factorial(n-1)] 을 통해 구할 수 있을 것이다. 여기서 한 가지 주의해야 하는데, k 가 의미하는 것은 순번을 의미하고 우리가 필요한 값은 인덱스(index)이다. 즉 배열의 index는 0부터 시작하므로 5번째의 순번은 곧 index 4와 같다. 따라서 초기 index 값은 k-1이 된다. 일단 factorial을 계산하는 과정이 필요하므로 이를 위한 함수를 하나 만들어주자.
// n의 최댓값이 20이기 때문에 재귀적으로 구현해도 된다.
// 여기서는 반복문을 이용해 구현했다.
// n은 자연수이므로 0이 입력으로 들어오는 경우는
// 고려하지 않아도 된다. 따라서 기본 리턴값은 1이다.
const factorial = (n) => {
let res = 1;
for(let i = 2; i <= n; i++) res *= i;
return res;
}arr[인덱스 / factorial(n-1)]에 대해 조금만 더 자세히 살펴보자. 위에서 직접 순열을 나열하며 보았지만 왜 이것이 성립하는 것일까?
위에서 언급한 주기와 관련이 있다. 각 순열을 앞자리 숫자를 기준으로 주기로 나눈다고 하면, 순열의 주기 단위는 factorial(n-1) 단위로 앞자리 숫자가 변경되게 된다. 그리고 문제에서 주어지는 k는 모든 순열 중에서 k번째에 위치한 순열을 의미한다. 즉 k-1를 factorial(n-1)이라는 주기로 나누게 되면 그 몫은 현재 주기에서의 맨 앞에 위치한 숫자의 인덱스(index)가 될 것이다.
예를 들어 [1,2,3,4,5] 인원이 줄을 설 때, 110번째 설 수 있는 방법을 구하려고 한다고 가정해보자. 먼저 모든 경우의 수는 5!으로 총 120가지이다. 그리고 이때 맨 앞 자리의 교체주기는 4!으로 24가 될 것이다. 즉 24를 기준으로 앞 자리의 숫자가 변경된다. 사이클을 직접 살펴보면 다음과 같다.
- 1 ~ 24 : 맨 앞자리 숫자 1 + [ ...나머지 4! ]
- 25 ~ 48 : 맨 앞자리 숫자 2 + [ ...나머지 4! ]
- 49 ~ 72 : 맨 앞자리 숫자 3 + [ ...나머지 4! ]
- 73 ~ 96 : 맨 앞자리 숫자 4 + [ ...나머지 4! ]
- 97 ~ 120 : 맨 앞자리 숫자 5 + [ ...나머지 4! ]
따라서 k-1 을 factorial(n-1) 로 나눈 그 몫은 배열 [1, 2, 3, 4, 5] 에서 현재 맨 앞자리 숫자의 index가 되는 것이다. (k-1을 하는 이유는 위에서 설명했다) 여기까지의 과정을 먼저 코드로 살펴보자.
// 인덱스와 일치를 위해 k - 1로 초기화한다.
let nth = k - 1;
// 주어진 n을 이용하여 [1, 2, 3, 4, ..., n] 형태의
// 배열을 만들어준다.
const arr = new Array(n).fill(1);
for(let i = 1; i < n; i++)
arr[i] = arr[i-1] + 1;
while(condition) {
...
// 주기를 구해주고
// 추후 n의 값은 arr.length 로 교체해줄것이다.
const fact = factorial(n-1);
// k-1 값을 주기로 나눈 몫을 구한다.
// 소수점 이하의 값이 나올 수 있으므로 버려준다.
const index = nth / fact >> 0;
...
}맨 앞자리는 구했는데 그렇다면 그 다음은 어떻게 또 구할 수 있을까? 이는 조금만 생각하면 쉽게 해결할 수 있다. 위에서 하나의 숫자를 고정하고서 주기를 구했다. 때문에 현재 주기에서 나타날 수 있는 경우의 수는 factorial(n-1) 개가 존재한다. 그런데 이 과정을 우리는 계속 반복해 줄 수 있다. 즉 factorial(n-1) 의 모든 경우의 수에서도 가장 앞에 위치하는 숫자를 고정시키고, 주기를 구하고 그 인덱스를 찾아갈 수 있다. 즉 n-1, n-2, n-3, ... 1 까지의 반복하며 현재 주기 단계에서 인덱스를 이용해 위치할 수 있는 맨 앞자리의 숫자를 찾아주는 것이다. 이를 위해서는 두 가지 작업이 추가적으로 더 구현되어야 한다.
- 인덱스 값을 다음 순열을 위해 재조정
- 사용한 배열의 원소를 제거
2번은 splice(index, 1)을 통해 간단하게 수행할 수 있다. 인덱스 값은 현재 주기에서 가장 앞자리의 숫자를 찾아주는 역할을 한다. 때문에 앞자리 숫자의 인덱스를 찾고 난후 다음 순열에서도 맨 앞자리를 찾을 수 있도록 k 값을 재조정해주어야 한다. 이 역시 간단하게 구할 수 있다. 현재 k-1의 값을 똑같이 factorial(n-1) 로 나눈 나머지가 다음 k 값이 될 것이다. 위에서 인덱스를 구한 예제를 다시 보자.
k=110 이고 주기가 24 였을때 맨 앞에 위치하게 될 숫자는 arr[109 / 24] 가 될 것이다. 이때 109 % 24 의 값은 자연스레 현재 순열에서 얼마만큼의 순번이 떨어져 있는지를 나타낸다. 이 값은 결코 24, 즉 factiorial(n-1)을 넘을 수 없고 이는 곧 다음 경우의 수에서의 맨 앞자리 숫자를 가리키는 인덱스를 동일한 로직으로 찾을 수 있다.
이때 하나만 더 주의하자. 만약 k의 값이 0이 되었다는 것은 정확하게 나누어 떨어졌다는 것을 의미한다. 이 경우 우리는 맨 앞에 위치한 원소를 사용하고 바로 제거해주고 있기 때문에, 지금 배열에 남아있는 원소 그대로 위치하게 됨을 의미한다. 따라서 nth === 0 이 되는 순간은 현재 배열을 바로 push 하고 반복문을 종료할 수 있다. 이를 코드로 나타내면 다음과 같다.
// 각 숫자를 넣을 배열 선언
const answer = [];
...
// arr = [1,2,3,4, ... n] 의 배열이다.
// 매 반복마다 사용한 숫자를 제거해줄 것이므로
// 배열의 원소가 모두 없어지는 경우 반복을 종료한다.
while(arr.length) {
// idx 가 0인 경우는 나누어 떨어진 경우이고
// 이는 지금 배열 그대로가 순번 그 자체임을 의미한다.
// 따라서 바로 반복문을 종료할 수 있다.
if(nth === 0) {
answer.push(...arr);
break;
}
...
// idx 값은 다음 순번을 위해 계속 갱신된다.
// 이는 idx 를 factorial(n-1)로 나눈 나머지 값이다.
nth = nth % fact;
// 맨 앞에 위치하는 숫자는 현재 배열[index]에 있다.
// 사용한 값은 반복해서 사용하지 않으므로 제거한다.
answer.push(arr[index]);
arr.splice(index, 1);
}
return answer;주석을 제외한 전체 코드는 다음과 같다.
코드
function solution (n, k) {
const answer = [];
const arr = new Array(n).fill(1);
for(let i = 1; i < n; i++) arr[i] = arr[i-1] + 1;
let nth = k-1;
while(arr.length) {
if(nth === 0) {
answer.push(...arr);
break;
}
const fact = factorial(arr.length - 1);
const index = nth / fact >> 0;
nth = nth % fact;
answer.push(arr[index]);
arr.splice(index, 1);
}
return answer;
}
const factorial = (n) => {
let res = 1;
for(let i = 2; i <= n; i++) res *= i;
return res;
}출처
