[프로그래머스] 줄 서는 방법 (C/C++)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/12936

코딩테스트 연습 - 줄 서는 방법

처음에는 next_permutation 함수를 이용해서 처음부터 순서대로 구했더니 시간초과가 났다.

그래서 맨 앞에 오는 숫자는 팩토리얼 값으로 k값을 나눴을 때 나오는 몫과 나머지를 이용해서 최대한 k의 크기를 줄여 나갔다.

 

배열의 길이가 5가 될 때 k줄이기를 멈추고 next_permutation으로 순열을 순차적으로 만들어서 값을 찾아내었고 효율성까지 통과했다.

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

vector<int> solution(int n, long long k) {
    long long factorial[21] = {0, 1, };
    for(long long index = 2; index <= 20; index++) {
        factorial[index] = index * factorial[index - 1];
    }

    vector<int> answer;
    vector<int> temp;

    for(int number = 1; number <= n; number++) {
        temp.push_back(number); 
    }

    int tempSize = temp.size();
    
    while(tempSize > 5) {
        long long number = factorial[tempSize - 1];
        long long share = k / number;
        long long remain = k % number;
        int index = (remain == 0 ? share : share + 1) - 1;

        answer.push_back(temp[index]);
        temp.erase(temp.begin() + index);

        k -= share * number; 
        tempSize--;
    }
    
    sort(temp.begin(), temp.end());

    do {
        k--;
        if(k == 0) {
            for(auto number : temp) {
                answer.push_back(number);
            }

            break;
        }
    }while(next_permutation(temp.begin(), temp.end()));
    
    return answer;
}