백준 1722번 순열의 순서 C++ 풀이

오늘은 1722번 문제의 풀이를 해보자.

 

순열의 순서 문제인데, 난이도가 높은 편인것 같다.

 

정답률이 30% 대 인만큼 난이도가 있지만, 이 내용은 앞으로도 꾸준히 쓰일 이론 같으니 잘 해두면 좋겠다.

 

문제 설명

 

간단히 설명하자면, 몇 번째 수열인지 입력하면 해당 수열을 구해서 출력하면 되고, 수열을 입력하면 몇 번째 수열인지 출력하면 된다.

 

숫자의 개수 N을 입력하고 1 또는 2를 입력한다.

 

1을 입력하면 몇 번째 수열을 구해야 하는지 k값을 입력하고, 2를 입력하면 몇 번째인지 구할 수열을 입력한다.

 

만약 N은 3을 입력하고 3번째 순열을 구하라고 한다면 (1, 2, 3), (1, 3, 2), (2, 1, 3) 이므로 (2, 1, 3)을 출력하면 된다.

 

N은 3을 입력하고 수열 (2, 1, 3)을 입력했다면 3을 출력하면 된다.

 

문제 풀이

 

그럼 이 문제를 어떻게 풀지 생각해보자.

 

경우의 수를 구해서 차감하는 방식으로 알고리즘을 구현하면 된다.

 

우선 factorial을 구현해 2!, 3! 같은 숫자를 구하는 기능을 만들면 된다.

 

그리고 1로 시작하는 경우의 수를 구한다면 fac(N-자리수) 처럼 구해서 제외해주면 된다.

 

예를 들어 첫 번째 자리가 1로 시작하는 세 자리 수열이 있다면, (1, 2, 3), (1, 3, 2)로 1로 시작하는 수열이 2개가 된다.

 

두 가지 기능을 구현해야 하는데, 우선 k번째 순열을 출력하는 방법부터 알아보자.

 

1) k번째 순열 구하기

 

k번째 수열을 구하기 위해서는 숫자의 자리 별로 몇 개의 경우의 수가 있는지를 계산하고, 자신보다 앞에 오는 경우의 수를 지워주는 방식으로 구현해야 한다.

 

만약 N이 3인 수열에서 3 번째 수열을 구한다고 가정하자.

 

첫 번째 자리에서 1로 시작하는 경우의 수는 fac(N-1)로 2개가 있다.

 

k는 3이므로 1로 시작하는 경우의 수인 2보다 크므로 첫 번째 자리는 1이 아님을 알 수 있다.

 

그러므로 k -= fac(N-1) 처럼 구현한다.

 

그리고 2로 시작하는 경우의 수는 fac(N-1)을 해보면 2개가 있을 것이다.

 

k는 1이므로 2로 시작하는 경우의 수 중 1번째 수열이 답이라는 것을 알 수 있다.

 

그럼 첫 번째 자리에서 2를 저장하고 두 번째 자리로 넘어간다.

 

이런 방식으로 마지막 자리까지 구해준다.

for(int i=1; i<=N; i++)  // 자리 수
{
    for(int j=1; j<=N; j++)  // 1~N까지 어떤 수를 배치할지 순서대로 확인
    {
        if(check[j])  // 이미 배치한 수는 pass
            continue;
        if(k>fac(N-i))  // 나머지 자리의 숫자들의 경우의 수보다 k가 크면
        {
            k -= fac(N-i);  // j로 시작하는 경우의 수는 빼주기
        }
        else
        {
            arr[i] = j;  // k가 더 크면 해당 자리는 j
            break;
        }
        check[arr[i]] = true;
    }
}

 

1부터 N까지 한 자리씩 숫자를 배치한다.

 

만약 k가 3이라고 하면, fac(N-i)로 j로 시작하는 수의 경우의 수를 구한다.

 

경우의 수가 더 크면 해당 자리 수는 그 수로 저장하면 되고, 그렇지 않으면 k에서 제외해준다.

 

아래 예시를 보자.

 

첫 번째 자리 수를 확인할 때 1로 시작하는 경우의 수는 fac(3-1)을 해보면 2!이 된다.

 

2개의 경우의 수가 있으므로 k에서 2개를 빼준다.

 

그럼 첫 번째 자리 수는 1로 시작하는 것이 아님을 알 수 있다.

 

1, 2, 3

1, 3, 2 -> 2!을 빼주면 여기까지는 제외된다. k는 1이 된다.

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1

 

k는 1이 되고, 다음 j를 확인한다.

 

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1

 

fac(N-1)를 확인하면 2이므로 k보다 크다.

 

그러므로 첫 번째 자리는 2가 된다.

 

2로 시작하는 경우의 수가 2가지가 있는데, k는 1이므로 2로 시작하는 경우의 수 중 첫 번째 수열이기 때문이다.

 

다음으로 2번째 자리수를 확인하자.

 

k는 1이고, fac(N-2)는 1이 된다.

 

그러므로 두 번째 자리는 1이 된다.

 

마지막으로 3번째 자리수를 확인하자.

 

k는 1이고, fac(N-3)은 1이 된다.

 

그러므로 세 번째 자리는 3이 된다.

 

이렇게 구한 수열을 출력해주면 첫 번째 기능 구현이 완료된다.

 

2) 몇 번째 수열인지 구하기

 

이번에는 주어진 수열이 몇 번째 인지 구하는 방법이다.

 

주어진 수열 앞의 수열들의 개수를 일정한 규칙에 따라 순차적으로 더해주면 된다.

 

주어진 수열 앞의 수열까지 더했을 때 해당 값에 1을 더해서 결과 값으로 출력하면 된다.

 

아래 수열을 보자.

 

1, 2, 3

1, 3, 2

2, 1, 3

2, 3, 1 -> 몇 번째인지 구할 수열

3, 1, 2

3, 2, 1

 

이 수열에서 2, 3, 1이 몇 번째인지 구하려면 우선 1로 시작하는 경우의 수를 구해서 결과에 더해준다.

 

(1, 2, 3), (1, 3, 2)로 두 개이므로 fac(N-1)을 하면 2!으로 구할 수 있다.

 

왜냐하면 1로 시작하는 수열은 뒤에 2개의 수가 있으므로 2!으로 구하는 것이다.

 

그리고 2, 3, 1은 2로 시작하기 때문에 2번째 자리로 넘어가서 생각한다.

 

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1

 

첫 번째 자리가 1일 경우는 이미 결과에 더해주었기 때문에 두 번째 자리인 1로 시작하는 수열의 개수를 결과에 더해준다.

 

2번째 자리이므로 두 번째 자리가 1로 시작하는 수열은 2, 1, 3 하나이다.

 

1 뒤에는 3 하나이므로 1!을 구하면 된다.

 

fac(N-2) 이므로 1이므로 결과에 더해준다.

for(int i=1; i<=N; i++)  // 1~N 자리수 확인
{
    for(int j=1; j<arr[i]; j++)  // i자리에 있는 숫자보다 작은 숫자로 시작하는 경우
    {
        if(check[j])
            continue;
        rst += fac(N-i);  // 더해주기
    }
    check[j] = true;
}

 

전체 코드

#include <iostream>

using namespace std;

long long arr[21] = {0, };  // 수열 저장
bool check[21] = {0, };
long long N, k, num;

long long fac(long long num)  // factorial 함수
{
    if(num==0 || num==1)
        return 1;
    return fac(num-1)*num;
}
int main()
{
    cin >> N >> num;
    if(num==1)
    {
        cin >> k;
        
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=N; j++)
            {
                if(check[j])
                    continue;
                if(k>fac(N-i))
                {
                    k -= fac(N-i);
                }
                else
                {
                    arr[i] = j;
                    check[j] = true;
                    break;
                }
            }
        }
        for(int i=1; i<=N; i++)
            cout << arr[i] << " ";
    }
    else
    {
        long long rst = 0;
        for(int i=1; i<=N; i++)
            cin >> arr[i];
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<arr[i]; j++)
            {
                if(check[j])
                    continue;
                rst += fac(N-i);
            }
            check[arr[i]] = true;
        }
        cout << rst+1 << endl;
    }
    return 0;
}