프로그래머스 - 줄 서는 방법

프로그래머스 - 줄 서는 방법

n과 k가 주어졌을 때, [1, 2, ..., n]까지의 순서를 순열로 나타냈을 때 k번째 순열을 반환하는 문제이다.
algorithm 라이브러리의 next_permutation을 써서 모든 순열을 구해가면서 k번째에서 break를 걸고 반환하면 정확성은 다 맞아도 효율성에서 틀린다.

이 문제는 세그먼트 트리 문제이다.
세그먼트 트리로 풀기 위해서는 먼저 k값의 상대적인 위치를 알아야한다.

만약 k값이 15라고 가정하면 답은 [3, 2, 1, 4]이다.
먼저 k값이 15일 때, ceil(15/3!)을 통해 첫 번째 원소가 세 번째 값인 것을 알 수 있다.
(4개중 1개를 제외한 나머지 3개로 나타낼 수 있는 순열의 갯수는 3!이기 때문에)

그렇다면 두 번째 원소를 알아야하는데, 이는 12로부터 상대적으로 3번째 위치에 의미한다는 것을 알 수 있다.

그렇다면 k값을 3이라고하고, 위와 동일한 방식으로 ceil(3/2!)을 통해 두 번째 원소는 두 번째 값인 것을 알 수 있다. 여기서 2라고 안하는 것은 상대적인 위치이기 때문이다.

예를 들어 k를 18이라고 가정하면 위 식을 반복했을 때, 첫 번째 원소는 세 번째 값, 두 번째 원소도 세 번째 값이 된다. 두 번째 등장한 세 번째 값이 의미하는 것은 1~n중 선택되지않은 나머지 원소 중 세 번째 값이라는 것을 의미한다. 첫 번째로 세 번째 값인 3이 선택되었기 때문에 두 번째로 선택되는 세 번째 값은 4가 된다. (이 과정을 세그먼트 트리로 빠르게 구해올 수 있다.)

위 방식을 n-1개의 원소에 대해서 반복해주고, 마지막 원소는 세그먼트 트리의 남은 값을 가져오면 된다.

코드는 다음과 같다.

#include <string>
#include <vector>
#include <cmath>
#include <map>

using namespace std;
long long factorial(int x)
{
    if(x == 1)
        return 1;
    return x * factorial(x - 1);
}
vector<int> segment;
map<int, int> idx_loc;
void init(int start, int end, int node)
{
    if(start == end) {
        segment[node] = 1;
        idx_loc.insert({node, start});
        return;
    }
    int mid = (start + end) / 2;
    init(start, mid, node * 2);
    init(mid + 1, end, node * 2 + 1);
    segment[node] = segment[node * 2] + segment[node * 2 + 1];
}

int query(int start, int end, int node, int idx)
{
    segment[node]--;
    if(start == end) {
        return idx_loc[node];
    }
    int mid = (start + end) / 2;
    if(idx > segment[node * 2])
        return query(mid + 1, end, node * 2 + 1, idx - segment[node * 2]);
    else
        return query(start, mid, node * 2, idx);
}
vector<int> solution(int n, long long k) {
    vector<int> answer;
    
    int treeHeight = ceil(log2(n));
    int treeSize = 1 << (treeHeight + 1);
    segment.resize(treeSize + 1, 0);
    init(1, n, 1);

    for(int i=n;i>1;i--) {
        long long facto = factorial(i - 1);
        int c = (int)ceil((double)k / facto);
        answer.push_back(query(1, n, 1, c));
        k -= facto * (c - 1);
    }
    answer.push_back(query(1, n, 1, 1));
    
    return answer;
}