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

programmers.co.kr/learn/courses/30/lessons/12936

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

next_permutation이나 DFS를 이용하여 모든 순열을 구해서 문제를 해결하면 효율성 테스트를 통과할 수 없습니다.

따라서 찾으려는 특정 순열만 바로 찾을 수 있게끔 구현해야합니다. 문제의 예제를 가져와 풀이를 설명해보도록 하겠습니다.

 

n = 3, k = 5의 조건을 가지고, 1~3의 숫자로 만들 수 있는 순열의 경우의 수는 다음과 같습니다. 그리고 여기서 모든 순열이 n개의 영역으로 분할되고, 각 영역은 (n-1)!개 입니다.

 

[1, 2, 3]

[1, 3, 2]          (n-1)! = (3-1)! = 2개

---------------

[2, 1, 3]

[2, 3, 1]

--------------- 

[3, 1, 2]

[3, 2, 1] 

---------------  n = 3개

 

또한 각 영역은 시작하는 숫자가 같은 것끼리 분할되어 있는 것을 확인할 수 있습니다. 예를들어 위의 예제에서는 다음과 같습니다.

 

1번째, 2번째([1, 2, 3], [1, 3, 2]) : 맨 앞의 숫자가 1 -> 인덱스 0

3번째, 4번째([2, 1, 3], [2, 3, 1]) : 맨 앞의 숫자가 2 -> 인덱스 1

5번째, 6번째([3, 1, 2], [3, 2, 1]) : 맨 앞의 숫자가 3 -> 인덱스 2

 

이를 인덱스에 매칭시킨다고 하면, (k - 1) / (n-1)! = (5 - 1) / (3 - 1)! = 2, 이런식으로 매칭시킬 수 있습니다.

방금 구한 인덱스가 가리키는 값을 answer 벡터에 넣어주고, 기존의 벡터에서는 해당 인덱스가 가리키는 값을 삭제합니다. 마지막으로 k = k % (n-1)! 식을 통하여 k를 갱신해주고, n의 값을 1 감소하는 과정을 반복합니다.

 

Flow

n = 3, k = 4(1을 빼줌)

answer = []

[1, 2, 3] - 0

[1, 3, 2] - 1    

[2, 1, 3] - 2

[2, 3, 1] - 3

[3, 1, 2] - 4

[3, 2, 1] - 5

 

n = 2, k = 0

answer = [3]

[1, 2] - 0

[2, 1] - 1

 

n = 1, k = 0

answer = [3, 1]

[2] - 0

 

n = 0, 종료

answer = [3, 1, 2]

 

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

long long factorial[21] = {1, }; // 팩토리얼 값을 미리 저장할 배열

vector<int> solution(int n, long long k) {
    vector<int> answer, v;
    
    for(int i = 1; i <= n; i++) {
        factorial[i] = factorial[i - 1] * i;
        v.push_back(i);
    }
    
    k--; // 인덱스 번호를 맞춰주기 위해 -1
    while(n > 0) {
        cout << n << " " << k << " ";
        int firstIdx = k / factorial[n - 1]; // k번째 순열의 첫번째 인덱스 찾기 
        answer.push_back(v[firstIdx]);  // 첫번째 인덱스가 가리키는 값을 answer에 더함
        v.erase(v.begin() + firstIdx); // 첫번째 인덱스가 가리키는 값을 v에서 삭제
        k %= factorial[n - 1]; // k번째 순열을 갱신   
        n--; // 사람의 수 감소(제거했으므로)
    }
    
    return answer;
}