[프로그래머스 - 12936] 줄 서는 방법 - C++

분류: 재귀, 경우의 수 /

 

문제

문제 링크

문제 설명

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! 이하의 자연수 입니다.

---

입출력 예

n	k	result
3	5	[3,1,2]

입출력 예시 설명

입출력 예 #1
문제의 예시와 같습니다.

 

풀이

- 경우의 수

#include <iostream>
#include <vector>
#include <list>

using namespace std;

vector<int> solution(int n, long long k) {
    long long tot = 1;
    list<int> pool = {1};
    for(int i=2; i<=n; i++) {
        tot *= i;
        pool.push_back(i);
    };
    
    vector<int> ans;
    for(int i=n; i>0; i--) {
        long long sub = tot/i;
        long long mx = sub;
        auto x = pool.begin();
        while(x != pool.end()) {
            if(k <= mx) {
                ans.push_back(*x);
                x = pool.erase(x);
                k -= mx - sub;
                tot = sub;
                break;
            } 
            mx += sub;
            ++x;
        }
    }
    return ans;
}

 

가장 처음 든 생각은 재귀, 백트래킹.

근데 굳이? subtree로 내려갔다가 백트래킹을 할 일이 없다. 처음부터 바로 목적지로 갈 수 있다.

 

`pool`은 현재 사용할 수 있는 수들을 의미한다. 초기값은 `{ 1 ~ n }`이다. `pool`은 ordered set의 역할을 한다. n번 크기 순서대로 순회하고 삭제하기 때문에 linked list인 `stl::list`로 선언했다.

`tot`은 `pool`로 만들 수 있는 순열의 전체 경우의 수를 의미한다. 초기값은 nPn으로 `n!`이다.

 

for문의 `i`는 각 자리의 경우의 수를 나타낸다. 

첫 번째 자리에는 `pool`의 n개의 모든 수가 올 수 있고, 두번째는 첫번째 에서 사용한 하나를 제외한 n-1개,...

이렇게 모두 곱해 n!

 

`sub`은 subtree의 경우의 수를 나타낸다. (다음 자릿수의 경우의 수.)

`x`는 `pool`의 `i`개의 원소 중 하나이다.

`mx`는 현재 `i`번째 자리에 `x`를 선택한 경우 subtree의 가장 오른쪽 leaf노드의 번호를 나타낸다.

`pool`은 오름차순이 보장되므로 `k <= mx`만 체크해 주면 된다.