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

[문제]

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

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

 

[풀이]

 

단순하게 C++ algorithm의 next_permutation으로는 문제를 풀 수 없습니다. 조건 중 n으로 입력되는 값이 20 이하인데, 만약 n이 20이 들어올 경우 조합의 갯수는 20!(2,432,902,008,176,640,000)이 됩니다.

 

고로 문제의 접근 방법을 조금 생각해봐야 합니다. 먼저 간단하게 { 1, 2, 3 }으로 조합을 만들어봅니다.

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

다음은 { 1, 2, 3, 4 }로 조합을 만들어봅니다.

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

 

조금 살펴보면, 특이한 점을 확인할 수 있습니다.

 

- 모든 조합의 경우의 수: n!

- 첫 번째 자리가 변하는 경우의 수 : (n-1)!

- 두 번째 자리가 변하는 경우의 수 : (n-2)!

- ...

 

결국 이 방식으로 파고 들어가면, k번째에 생성되는 조합은 어떤 경우를 갖는지 알아낼 수 있습니다. { 1, 2, 3 } 수열에서 5번째로 오는 값을 찾는 과정을 아래의 함수로 살펴보겠습니다.

long long factorial(int _Num)
{
    long long Result = 1;
    for (int i = 1; i <= _Num; ++i)
    {
        Result = Result * i;
    }
    return Result;
}

// ...
--k;
for (int i = 0; i < n; ++i)
{
    long long Value = factorial(n - 1 - i);
    long long Index = k / Value;
    k %= Value;

    if (Index >= Numbers.size())
    {
        Index = Numbers.size() - 1;
    }

    answer.push_back(Numbers[Index]);
    Numbers.erase(Numbers.begin() + Index);
}

 

1. --k : 인덱스는 0부터 계산하기 때문에, 1을 빼서 활용

2. n = 3일 때, 가능한 순열 수는 3! = 6 입니다.

3. i = 0 일 경우

- Value는 (3-1-0)! = 2! = 2

- Index는 4 / 2 = 2

- k %= Value는 0

- 이로써 3이 선택되고, 1. 2가 남습니다.

4. i = 1 일 경우

- Value는 (3-1-1)! = 1! = 1

- Index는 0 / 1 = 0

- k %= Value는 0

- 이로써 1이 선택되고, 2가 남습니다.

4. i = 2 일 경우

- Value는 (3-1-2)! = 0! = 1

- Index는 0 / 1 = 0

- k %= Value는 0

- 이로써 2가 선택되고, 종료됩니다.

 

결론은 전체 경우의 수 중 5번째의 경우로 3을 선택하고, 그 안에서 다시 첫 번째로 와야하는 경우로 1을 선택하고, 이 과정을 반복하는 것입니다.

#include <string>
#include <vector>

using namespace std;

long long factorial(int _Num)
{
    long long Result = 1;
    for (int i = 1; i <= _Num; ++i)
    {
        Result = Result * i;
    }
    return Result;
}

vector<int> solution(int n, long long k)
{
    vector<int> answer;
    vector<long long> Numbers;
    for (int i = 1; i <= n; ++i)
    {
        Numbers.push_back(i);
    }

    --k;
    for (int i = 0; i < n; ++i)
    {
        long long Value = factorial(n - 1 - i);
        long long Index = k / Value;
        k %= Value;

        if (Index >= Numbers.size())
        {
            Index = Numbers.size() - 1;
        }

        answer.push_back(Numbers[Index]);
        Numbers.erase(Numbers.begin() + Index);
    }

    return answer;
}