백준) 9742 순열

9742. 순열

문제

집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {2,3,5}의 순열은 다음과 같다.

1. 2 3 5
2. 2 5 3
3. 3 2 5
4. 3 5 2
5. 5 2 3
6. 5 3 2

각각의 순열은 숫자로 나타낼 수 있다. 위의 순열은 사전순으로 쓰여져 있으며, 등장하는 순서를 이용해 나타낸다. 즉, 3 5 2는 위치 4에 있고, 5 3 2는 마지막 위치인 6에 있다.

서로 다른 숫자와 문자로 이루어진 집합과 위치가 주어졌을 때, 그 집합의 순열 중 주어진 위치의 순열을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전순 순서대로 주어진다. 문자열 다음에는 찾아야 하는 위치가 주어진다.

출력

각각의 테스트 케이스마다, 입력으로 주어진 위치에 해당하는 순열을 공백없이 출력한다. 만약, 해당하는 순열이 없는 경우에는 "No permutation"을 출력한다.

예제 입력 

235 4
bein 20
123456 700
mnpqr 130
tuvwxyz 4000

예제 출력 

235 4 = 352
bein 20 = nbie
123456 700 = 651342
mnpqr 130 = No permutation
tuvwxyz 4000 = ywuxvzt 

1. 접근

순열을 만드는 규칙이 정해져있고, 몇 번째 순열을 출력해야 하는지 주어진다.

규칙은, 우리가 보통 경우의 수를 찾는 방법과 동일하다.

1,2,3,4 라면, 첫 번째 자리에 가장 작은 1을 적는다. 두 번째 자리엔 2,3,4 가 올 수 있다. 그 중 가장 작은 2을 적는다. ...

첫 번째 자리의 경우를 모두 적었으면, 그 다음으로 작은 2를 적고 동일한 과정을 반복한다.

당연히 (글자길이!)를 넘어가는 k번 째 순열을 존재하지 않으므로, 전처리로 팩토리얼을 미리 계산해주면 없는 경우는 쉽게 알 수 있다.

다만 위와같이 해당 순열을 빠르게 찾으려면 어떻게 해야할까?

2-1). 풀이 1

놀랍게도 알고리즘 헤더에는 위와 같은 문제를 해결해주는 함수가 기존재한다.

바로 next_permutation(iterator first, iterator last) 인데, 이 함수는 [first, last) 범위 안의 원소들을 다음 "사전 순서"로 정렬해준다.

사전 순서란 우리의 규칙과 동일하게 적용된다.

영어사전의 단어들이 어떤 순서로 소개되는지 생각해보면 된다.

그러면 간단하게 함수호출로 문제를 풀 수 있을 것이다. k번 째 순열을 찾기 위해서 함수를 k번 호출하면 될 것이다.

2-2). 풀이 2

그러면 저 함수는 어떻게 구현되어 있는 걸까?

다음에서 정보를 얻었다.

https://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation

사전 순으로 1,4,3,2 의 다음 순열은 2,1,3,4 이다.

눈치 깔 수 있는 것은, 1의 오른쪽이 전부 내림차순이면 1의 자리수는 다음으로 큰 수로 바뀌고, 나머지는 오름차순으로 다시 정렬된다는 것이다.

마찬가지로, 1,3,4,2의 다음 순열은 1,4,2,3 이다.

오른쪽이 전부 오름차순이 아니게 되는 첫번째 원소는 3이었다. 그러면 3은 다음으로 큰 수로 바뀌고, 나머지는 오름차순으로 다시 정렬된다.

그러면 구현해야 할 것은 두 가지다. 

1. 오름차순이 아니게 되는 원소를 뒤에서 부터 찾은 다음, 그 원소보다 다음으로 큰 수를 찾아야하고

2. 나머지를 오름차순으로 정렬해야 한다.

1번은 쉽게 할 수 있다. 우리가 찾은 원소는 오른쪽이 오름차순이 아니게 되는 첫 원소이므로, 다음으로 큰 수는 뒤에서 부터 원소보다 처음으로 큰 수다.

2번은 그냥 sort를 쓸 수도 있겠지만, 다음과 같이 더 빠르게 수행할 수 있다.

먼저 1번에서 찾은 원소와 다음으로 큰 수를 서로 바꾼다. 1,3,4,2 였다면 3과 4를 바꿔서 1,4,3,2가 되었을 것이다.

우리가 찾은 원소는 오른쪽이 오름차순이 아니게 되는 첫 원소이므로, 나머지 두 자리수는 자명히 내림차순이다. 따라서 역순으로 뒤집어 주면 된다.

-> 1,4,2,3

1,4,5,3,2 의 다음 사전 순 순열은 1,5,2,3,4 이다. 1번을 수행하고 찾은 원소는 4다. 4보다 큰 수는 5임을 뒤에서 부터 찾을 수 있다.

4와 5를 바꾼다. 1,5,4,3,2 가 된다. 당연히 5의 오른쪽은 전부 내림차순이다. 오른쪽을 전부 뒤집어주자. -> 1,5,2,3,4 

2-3) 풀이 3

사실 수학적으로도 풀 수 있다.

1,2,3,4 로 4자리의 순열이라면, 총 4! = 24의 경우가 있는데, 이는 크게 첫 자리별로 4개의 집합으로 분류할 수 있다.

또 각각의 집합 안에서, 남은 세 자리 중에 첫 자리(실제론 두번째 자리)별로 3개의 집합으로 분류할 수 있다.

예를 들어, a,b,c,d 의 17번째 사전 순 순열을 알고 싶다면, 첫 자리별로 3! = 6 의 경우를 갖고 있으니까 16 / 6 = 2다.

(모듈러 연산을 위해 0, 1, 2, ... 순으로 순서를 매기자.)

이는 첫 자리가 arr[2] = c 임을 알려준다.

남은 세 자리에 대해 생각해보면 총 6가지 경우가 있으니까 16 % 6 = 4다. 이 말은 그 집합 안에서 다섯번째 순열이란 뜻이다.

4를 2!으로 나누면 2가 나온다. 이 말은 두 번째 자리가 남은 a, b, d 중 arr[2] = d 라는 뜻이다.

남은 두 자리에 대해 생각해보면 총 2 가지 경우가 있으니까 4 % 2 = 0이다. 이는 그 집합 안에서 첫번째 순열이란 뜻이다.

0을 1!으로 나누면 0이 나온다. 이는 세 번째 자리가 남은 a, b 중 arr[0] = a 라는 뜻이다.

이제 구현은 재귀적으로 할 수 있다.

자리 수를 채워나가면서 맨 앞자리를 가리키는 포인터를 전진시키면서 넘겨주면 된다. 

3-1) 코드 1

#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int fact[12] = { 1, };
 
int main() {
 
    for (int i = 1; i <= 10; i++)
        fact[i] = fact[i - 1] * i;
 
    string a;
    int n;
 
    while (cin >> a >> n) {
 
        cout << a << " " << n << " = ";
 
        if (n > fact[a.length()]) {
            cout << "No permutation" << endl;
            continue;
        }
 
        int cnt = 0;
        do {
            cnt++;
            if (cnt == n) {
                cout << a << endl;
                break;
            }
        } while (next_permutation(a.begin(), a.end()));
    }
 
    return 0;
}

3-2) 코드 2

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n, k;
int fact[12];
int num[11];
char str[20];
 
bool next_per(int x, int y) {
    if (x == y)
        return false;
 
    int i = y;
 
    while (1) {
        int j = i;
        --i;
 
        if (num[i] < num[j]) {
            int k = y + 1;
            
            while (!(num[i] < num[--k]));
 
            int tmp = num[i];
            num[i] = num[k];
            num[k] = tmp;
 
            for (int t1 = j, t2 = y; t1 <= (j + y) / 2; ++t1, --t2) {
                int tmp = num[t1];
                num[t1] = num[t2];
                num[t2] = tmp;
            }
            return true;
        }
 
        else if (i == x) {
            for (int t1 = x, t2 = y; t1 <= (x + y) / 2; ++t1, --t2) {
                int tmp = num[t1];
                num[t1] = num[t2];
                num[t2] = tmp;
            }
            return false;
        }
    }
}
 
int main() {
    fact[0] = 1;
    for (int i = 1; i <= 10; i++) {
        fact[i] = fact[i - 1] * i;
    }
        
    while (~scanf("%s %d", str, &k)) {
        n = strlen(str);
        for (int i = 0; i < n; ++i)
            num[i] = i;
        int cnt = 0;
 
        printf("%s %d = ", str, k);
        if (k > fact[n] || k <= 0)
            puts("No permutation");
        else {
            while (++cnt != k)
                next_per(0, n - 1);
 
            for (int i = 0; i < n; ++i)
                printf("%c", str[num[i]]);
            puts("");
        }
    }
    return 0;
}

3-3) 코드 3

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n, k;
int fact[12] = { 1, };
char str[20];
 
void func(char *s, int x, int f) {
    if (f < 1) return;
 
    int i = x / fact[f - 1];
    int last = s[i];
 
    while (i-- > 0)
        s[i + 1] = s[i];
    
    s[0] = last;
 
    func(s + 1, x % fact[f - 1], f - 1);
}
 
int main() {
    for (int i = 1; i <= 10; i++)
        fact[i] = fact[i - 1] * i;
 
    while (scanf("%s %d", str, &k) != EOF) {
        n = strlen(str);
 
        printf("%s %d = ", str, k--);
 
        if (k >= fact[n] || k < 0)
            puts("No permutation");
 
        else {
            func(str, k, n);
            puts(str);
        }
    }
 
    return 0;
}

4. 후기

처음엔 계속 배열을 두고 쓴 자리수를 체크체크하는 무지막지한 방법으로 124ms로 들어왔었다.

풀이 1 : 12 ms

풀이 2 : 20 ms

풀이 3 : 0 ms