[프로그래머스 lv2] 줄서는 방법 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

가장 먼저, next_permutation()이나 재귀 함수를 이용해서 모든 경우의 수를 탐색하고 K번째 순열을 리턴하는 방법이 떠오른다.

하지만, 이 방법으로 제출하면 효율성 테스트에서 TLE 가 발생한다.

규칙을 찾아 더 간단한 방법으로 문제를 해결해보자.

 

예를 들어, n = 4, k = 10 일 때 순열은 다음과 같다.

 

[0 번째] 1 2 3 4

[1 번째] 1 2 4 3

[2 번째] 1 3 2 4

[3 번째] 1 3 4 2

[4 번째] 1 4 2 3

[5 번째] 1 4 3 2

----------------------

[6 번째] 2 1 3 4

[7 번째] 2 1 4 3

[8 번째] 2 3 1 4

[9 번째] 2 3 4 1

[10번째] 2 4 1 3  (k = 10)

[11번째] 2 4 3 1

----------------------

[12번째] 3 1 2 4 

...

 

첫번째 자리를 살펴보면, 각 숫자가 (n-1)!개씩 반복되는 것을 알 수 있다.

따라서, k를 (n-1)! 으로 나누면 첫번째 글자가 1, 2, 3, 4 중 몇번째 수인지 인덱스를 알 수 있다.

예시를 보면, 10/3! = 1 이므로, [1, 2, 3, 4] 중 인덱스 1번인 2가 첫번째 원소가 된다.

 

첫번째 수를 결정하고, (n-1)!개의 순열만 떼와서 두번째 숫자를 결정해보자.

 

[0 번째] 2 1 3 4

[1 번째] 2 1 4 3

----------------------

[2 번째] 2 3 1 4

[3 번째] 2 3 4 1

----------------------

[4번째] 2 4 1 3 (k = 4)

[5번째] 2 4 3 1

 

이 때, k를 새로운 인덱스로 업데이트 해야 하는데,  k = k%(n-1)! 으로 업데이트 하면, k = 4가 된다. 

첫번째 수는 이미 결정했으므로 n을 하나 줄이고, [1, 2, 3, 4]에서 이미 사용한 수 2는 제거하여 [1, 3, 4]의 후보를 둔다.

 

첫번째 자리를 결정할 때와 마찬가지로, 두번째 자리의 수들은 (n-1)!씩 반복된다. 

따라서 k를 (n-1)!으로 나누면 두번째 수가 후보 중에서 몇번째 인덱스에 위치하는지 알 수 있다.

예시를 보면, 4/2! = 2이므로, [1, 3, 4] 중 인덱스가 2번인 4가 두번째 원소가 된다.

 

두번째 수를 결정하고, 다시 (n-1)! 개의 순열만 떼와서 세번째 숫자를 결정해 보자.

 

[0번째] 2 4 1 3 (k = 0)

----------------------

[1번째] 2 4 3 1

 

 이 때, k를 새로운 인덱스로 업데이트 해야 하는데, k = k%(n-1)! 으로 업데이트 하면, k = 0이 된다.

두번째 수까지 결정했으므로 n을 하나 줄이고, [1, 3, 4]에서 이미 사용한 수 4는 제거하여 [1, 3]의 후보를 둔다.

 

두번째 자리를 결정할 때와 마찬가지로, 세번째 자리의 수들은 (n-1)!씩 반복된다.

따라서 k를 (n-1)!으로 나누면 세번째 수가 후보 중에서 몇번째 인덱스에 위치하는지 알 수 있다.

예시를 보면, 0/1! = 0 이므로, [1, 3] 중 인덱스가 0번인 1이 세번째 원소가 된다.

 

해당 과정을 마지막까지 반복하면 k번째 수가 순열을 구할 수 있다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

long long fac(int n) {
    if (n == 0) return 1;
    return n*fac(n-1);
}

vector<int> solution(int n, long long k) {
 
    k--; //0부터 시작하는 인덱스로 계산하기 위해 1뺌
    vector<int> v;
    for (int i=1; i<=n; i++) v.push_back(i);
    
    vector<int> ans;
    for (int i=n; i>=1; i--) {
        int idx = k/fac(i-1);
        ans.push_back(v[idx]);
        v.erase(v.begin()+idx);
        k = k%fac(i-1);
    }
    return ans;
}