C++:: 프로그래머스 < 줄 서는 방법 >

처음에는 next_permutation이라는 함수를 사용하여 풀어보았지만 시간초과가 나서 다음과 같은 방법으로 풀었다.

시간 초과 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, long long k) {
    vector<int> answer;
    for (int i=1; i<=n; i++) answer.push_back(i);
    for (int i=1; i<k; i++) {
        next_permutation(answer.begin(), answer.end());
    }
    return answer;
}

통과 풀이

#include <string>
#include <vector>
using namespace std;

long long range(int n) {
    long long res = 1;
    while (--n) res *= n;
    return res;
}

int findNum(int idx, vector<bool>& vis) {// 사용안한 수들중 인덱스 번쨰의 수 리턴
    int cnt = 1;

    for (int i=1; i<vis.size(); i++) {
        if (vis[i]) continue ;
        if (cnt == idx) {
            vis[i] = true;
            return i;
        }
        cnt++;
    }
}

vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<bool> vis(n+1, false);// 사용한 숫자인지 체크
    long long r = 2;
    
    while (r > 1) {
        r = range(n--);// n! 을 n으로 나누어준 범위 곧 (n-1)!, 예시로 숫자 3개에 대해서는 2!인 2가 범위이다. 
        int idx = 1;
        while (r * idx < k) {// 현재 어느 범위에 속하는 인덱스인지 구한다, 사용하지 않은 수들중 몇번째로 큰 수인지
            idx++;
        }
        answer.push_back(findNum(idx, vis));
        k -= r * (idx - 1);// 앞에 몇번째 까지인지는 빼주면 된다.
    }
    for (int i=1; i<vis.size() ;i++) if (!vis[i]) answer.push_back(i);// 마지막으로 사용안한수 추가
    return answer;
}

통과풀이에대한 풀이 예시를 간단하게 설명하자면
예시로 n = 5, k = 51이라 가정하자.
n=5일때 나올수있는 정렬 가지수는 5! = 120 이고 이를 n개로 쪼개어서 구간으로 생각하면 구간 r = 24이다.
이때 구간으로 쪼개어서 생각하는 이유는 구간범위 인덱스가 곧 첫번째 시작 숫자이기 떄문이다.
1 ~ 24 범위에서는 첫 시작 숫자 1, 25 ~ 48 => 2 ,.... 97 ~ 120 => 5 와같다고 볼 수 있다.

따라서 k = 51은 49 ~ 72 범위 내이므로 첫 시작이 3이된다.
k -= 49 => k = 3 와같이 현재 범위 첫시작을 뺴주어서 갱신도 해준다. 다음 범위에서의 순서도 알아야하기 때문이다.
이다음에는 n개의 숫자중 1를 골랐으므로 n-1에 대해 똑같이 실행하되 이미 고른 숫자에 대해서 주의해주면 된다.
이를 숫자를 다 고를때까지 반복해주면된다.