C++ / 프로그래머스 / 줄 서는 방법

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

 

문제풀이

 

처음에는 간단하게 next_permutation을 이용하여 구하려고 했지만 시간초과로 인해 방법을 바꿨다.

 

조합의 가지 수를 구하는 경우를 생각하면 된다.

맨 앞자리는 n! 의 사람이 올 수 있다.

그다음 자리는 (n-1)! 의 사람이 올 수 있다.

 

문제의 예제를 보면 n이 3이고 k가 1일 때 [1, 2, 3]이다.

k가 2일 때는 [1, 3, 2]이고, k가 3일 때는 맨 앞자리 번호가 바뀌어 [2, 1, 3]이 된다.

맨 앞자리가 바뀌는 사이클은 (n-1)!=2이다.

줄 서는 첫 번째 방법과 두 번째 방법은 맨 앞은 1번의 사람이 서 있게 된다.

하지만 1/2와 2/2는 다르므로 계산하기 편하게 주어진 k에 1을 빼고 계산했다.

그리고 맨 앞부터 구할 것이므로 n-idx-1의 팩토리얼을 저장하는 벡터를 따로 만들어 저장한다.

 

그리고 번호는 1번부터 시작하고 같은 번호는 존재할 수 없으므로 따로 숫자 벡터를 만들어 1부터 n까지 저장한다.

 

이제 반복문을 반복하면서 answer[idx]에는 남은 숫자 중 k / 미리 저장한 팩토리얼[idx]의 값을 저장하고

해당 숫자를 사용했으므로 숫자 벡터에서 idx번째 숫자를 지운다.

그리고 해당 자리를 구했으므로, k에서 (k / 팩토리얼) * 팩토리얼 값을 뺀다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

vector<int> solution(int n, long long k) {
    vector<int>answer(n, 0);
    vector<int>number(n + 1, 0);
    vector<ll>factorial(n, 0);
    --k;

    for (int idx = 0; idx < n; ++idx) number[idx] = idx + 1;

    ll num(2);
    if (n > 1) factorial[n - 2] = 1;
    for (int idx = n - 3; idx >= 0; --idx) {
        factorial[idx] = factorial[idx + 1] * num;
        ++num;
    }

    for (int idx = 0; idx < n; ++idx) {
        if (factorial[idx] == 0) answer[idx] = number[0];
        else {
            answer[idx] = number[k / factorial[idx]];
            number.erase(number.begin() + k / factorial[idx]);
            k -= k / factorial[idx] * factorial[idx];
        }
    }

    return answer;
}