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

문제

---

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

풀이

---

제시된 배열 원소들을 순열로 나열할 때, k번째 순열을 구하는 문제이다. 단순하게 모든 순열을 구하면 제한 조건이 20까지 이므로, 시간 초과가 발생한다. 따라서 순열의 규칙을 활용, 원소가 등장할 순서를 계산하여 k번째 순열을 구한다.

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

using namespace std;

vector<int> solution(int n, long long k) 
{
    vector<int> answer;
    stack<long long> st;
    long long result = 1;
    vector <long long> people;

    people.push_back(1);

    for (int i = 1; i < n; i++)
    {
        result *= i;
        st.push(result);
        people.push_back(i + 1);
    }

    long long div = k / st.top();
    long long res = k % st.top();

    for (int i = 0; i < n; i++)
    {
        if (res == 0)
        {
            answer.push_back(people[div - 1]);
            people.erase(people.begin() + div - 1);
            sort(people.begin(),people.end(), greater<long long>());
            answer.insert(end(answer), begin(people), end(people));

            break;
        }

        else
        {
            answer.push_back(people[div]);
            people.erase(people.begin() + div);
            st.pop();

            div = res / st.top();
            res = res % st.top();
        }
    }

    return answer;
}