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

[문제]

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

---

입출력 예

 

3

5

[3,1,2]

 

[풀이]

 

1) 넥퍼뮤를 사용하면 시간복잡도가 o(n!) 이기 때문에 정확도 테스트는 통과하지만 효율성 테스트에서 시간초과가 난다. 

 

2) 그래서 dfs로 조합만들기를 하다가 row 배열이 계속 변경되는 것을 유지하도록 하는 게 어려워서 그냥 조합을 사용했다. 

 

3) 각 자리마다 인덱스 값을 찾아나서야 한다. 

 

[1,2,3,4] 이렇게 4명이 있다고 할 때 k = 8인 경우를 본다면 

첫번째 자리에는 1-n만큼의 숫자가 올 수 있고 0은 허용되지 않는다. 

각자 (n-1)! 만큼의 경우의 수를 가지고 있다. 

(n-1)! -> 6개씩 올 수 있다, 

이 특징을 사용해서 제일 앞의 숫자를 구할 수 있다. 

1: 1-6

2: 6-12 

----현재 만든 결과-----[2, , , ] ----남은 숫자-----[1 ,3 ,4 ]

 

일반화를 하면 몫이 인덱스가 된다.

k / (n-1)! => 8/6 = 몫 : 1 / 나머지 : 2

 

k는 나머지가 되야 한다. (2로 시작하는 경우의 수 중 2번째를 구해야 하니까)

 

-----k = 2----

첫번째 자리수를 뽑았으니 이제 남은 경우의 수는 (n-2)! 이다. 

k / (n-2)! => 2 / 2 = 몫 : 1 / 나머지 0

 

** 나머지가 0인  경우에는 (몫 - 1) 의 인덱스를 가져와야 한다! 

그룹의 마지막 숫자까지 살펴보았기 때문에(k가 0이 된다) 남은 숫자들을 역순 배치해서 넣어준다. 

 

----현재 만든 결과-----[2, 1, , ] ----남은 숫자-----[3 ,4 ]

 

역순으로 넣어준다.

----현재 만든 결과-----[2,1 ,4 , 3] ----남은 숫자-----[]

 

---

#include <string>
#include <vector>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
 
vector<int> solution(int n, long long k) {
    vector<int> answer;
    
    //factorial을 이용한다. 
    /*
    전체 경우의 수가 3! 일때 k=5번째 경우의 수를 구하라 
    앞 사람부터 순서대로 채워나간다. 
    첫번째 인덱스에는 1~n까지 모든 숫자가 올 수 있고, 각각 (n-1)! 의 경우의 수를 가진다. 
    (3-1)! => 2개씩 
    
    //////////////////
    첫번째 인덱스에 올 수 있는 숫자는 k와 (n-1)!로 구할 수 있다. 
    k가 5라면 5/2 -> 몫 : 2 / 나머지 1
    몫이 2라는 것은 우리가 구하고자 하는 케이스가 3이 첫번째인 경우 중 1번째 경우의 수를 말한다. 
    
    몫이 가르키는 인덱스값을 가져온다. 
    첫번째 인덱스는 [3, ,]
    남은 숫자는 [1,2]
    
    나머지가 0인 경우에는 그룹의 마지막에 도달했다는 것이다. 
    나머지가 0인 경우에는 몫-1 을 해서 인덱스가 가르키는 값을 가져온다. 
    
    마지막으로 row에 남은 숫자들을 결과  배열에 넣어준다. (안 해주면 안됨 )
    
    *****넥퍼뮤는 효율성에서 시간 초과 발생 (o(n! )이기 때문에 )
    */
    
    ll fact = 1;
    vector<int> row;
    
    for (int i = 1; i <=n; i++) {
        fact *= i;
        row.push_back(i);
    }
    
    //사전 준비 
    int res[n];
    memset(res, 0, sizeof(res));
    int idx= 0;
    
    while(n>0) {
        //마지막 사람까지 모두 뽑을 때까지 반복 
        fact /= n--; //(n-1)!
        
        //몫이 가르키는 인덱스값을 가져온다. 
        int tmp_idx =(int) (k / fact); //typecasting 필요  
        int tmp_remain = (int) (k% fact);
        
        if (tmp_remain == 0) {
            //나머지가 0인 경우 맨 앞의 숫자를 가져온다. 
            tmp_idx--;
            res[idx++] = row.at(tmp_idx);
            row.erase(row.begin() + tmp_idx); //남아있는 숫자에서 뽑은 숫자를 제거한다. 
            break; //그룹의 마지막 숫자에 도달함 
        } 
        res[idx++] = row.at(tmp_idx);
        row.erase(row.begin() + tmp_idx); //남아있는 숫자에서 뽑은 숫자를 제거한다. 
        
        k %= fact;
        
    }
    
    for (int i = 0; i < idx; i++) {
        answer.push_back(res[i]);
    }
    
    for (int i = row.size()-1; i>=0; i--) {
        //row에 남은 숫자들을 넣어둔다. 
        answer.push_back(row.at(i)); //역순 배열 
    }
// 넥퍼뮤는 시간 초과 발생 (효울성테스트) 
//     int idx = 1;
//     do {
//         if (idx == k) {
//             answer = row;
//         }
//         idx++;
//     } while(next_permutation(row.begin(), row.end()));
    return answer;
}