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

---

🔗 문제 링크

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

프로그래머스

 

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

vector<long long> GetFactorials(int n){
    vector<long long> factorial(n+1, 1);
    
    for(int i=2; i<=n; i++){
        factorial[i] = factorial[i-1] * i;
    }
    
    return factorial;
}

vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<long long> weights = GetFactorials(n-1);
    vector<bool> used(n + 1, false);
    
    k--;

    for (int i = 0; i < n; i++) {
        long long value = k / weights[n - 1 - i];
        int count = 0;
        
        for (int j = 1; j <= n; j++) {
            if (!used[j]) {
                if (count == value) {
                    answer.push_back(j);
                    used[j] = true;
                    break;
                }
                count++;
            }
        }
        
        k %= weights[n - 1 - i];
    }
    
    return answer;
}

---

📝 풀이

각 자릿수에 가능한 경우의 수는 (n-1)!입니다.

이를 이용하기 위해 미리 1부터 n-1까지 팩토리얼 값을 구하는 GetFactorials 함수를 구현합니다.

1부터 n까지의 숫자를 중복없이 사용하기 위해 vector<bool> used를 n+1 크기로 초기화 합니다.

k를 index로 활용하기 위해 1를 빼줍니다.

 

k를 i의 가중치로 나누어 현재 자릿수에 들어가야 하는 숫자를 구합니다.

사용되지 않은 숫자 중 value번째가 현재 자릿수에 들어가야 하는 숫자입니다.

해당 숫자를 찾았으면 answer에 psuh 합니다.

이후 k를 갱신하고 이 과정을 n번 반복합니다.

최종적으로 나열된 answer를 return 합니다.