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

접근법:

숫자를 준비한다.
모든 순열을 만들어서 저장한다.
이를 사전순으로 정렬한다.
컨테이너에서 k 번째 순열을 결과로 삼는다.

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

long long factorial(int n)
{
    if(n == 1) return 1;
    return n * factorial(n - 1);
}

vector<int> solution(int n, long long k) {
    vector<int> answer(n);
    for(int i = 0; i < n; ++i)
        answer[i] = i + 1;
    vector<vector<int>> temp(factorial(n));
    int i = 0;
    do
    {
        temp[i] = answer;
        ++i;
    } while(next_permutation(answer.begin(), answer.end()));            
    sort(temp.begin(), temp.end());
    
    return temp[k-1];
}

이 방법은 예제는 맞았지만, 시간및 메모리 초과로 인해 테스트 통과가 불가능 했습니다. 그래서

접근법:

숫자 리스트와 팩토리얼을 구합니다.
각자리의 숫자를 하나씩 정합니다.
1. 현재 자리 숫자를 제외한 나머지 숫자로 만들수 있는 경우의 수 = (n-1)!
2. 리스트에서 몇 번째 숫자를 골라야하는지 계산합니다.
3. 선택한 숫자를 리스트에서 제거
4. 다음 자리를 찾기위해서 k를 갱신합니다.
결과를 리턴

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

vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<int> numbers(n);
    long long fact = 1;
    for(int i = 0; i < n; ++i)
    {
        numbers[i] = i + 1;
        fact *= (i + 1);
    }
        
    k--;
    
    while(n > 0)
    {
        fact /= n;
        
        int idx = k / fact;
        answer.push_back(numbers[idx]);
        numbers.erase(numbers.begin() + idx);
        
        k %= fact;
        n--;
    }
    
    return answer;
}

bookmark

점프와 순간이동[프로그래머스]

행렬 테두리 회전하기[프로그래머스]