[백준 1722] 순열의 순서

문제 : https://www.acmicpc.net/problem/1722

문제를 처음에 보고 너무 쉽게 생각했는지, 직접 구현한 배열의 next_permutation을 사용했다.

하지만, 시간초과... next_permutation으로 문제를 풀면 Big-O 표기로

O(N!)이 나오기 때문이였다.

항상 분발하는 자세로 겸손히 공부해야겠다. ㅠㅠ

실패한 코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
bool next_permutation(int *a, int n){
    int i = n-1;                    // 뒤부터 시작 
    while(i > 0 && a[i] <= a[i-1])    // 어디까지가 감소수열인가?? 
        i -= 1;
    if(i <= 0)                        // 전체가 감소수열이다. 
        return false;                // 다음 수열은 존재하지 않는다.
    int j = n-1;
    while(a[i-1] >= a[j])
        j -= 1;
    swap(a[i-1],a[j]);
    j = n - 1;
    while(i < j){
        swap(a[i],a[j]);
        i +=1;
        j -=1;
    }
    return true;
}
void problem1(int *a, int m, int size){
    for(int i = 0; i < size; i++)
        a[i] = i+1;
        
    for(int i = 0; i < m-1; i++)
        next_permutation(a,size);
    
    for(int i = 0; i < size; i++)
        cout << a[i] << ' ';
    cout << '\n';
    
    return;    
}
void problem2(int *a, int size){
    int *b = new int[size];
    int cnt = 1;
    
    for(int i = 0; i < size; i++)
        b[i] = i+1;
        
    while(1){
        for(int i = 0; i < size; i++){
            if(b[i] != a[i])
                break;
            else if(i == size-1){
                cout << cnt;
                return;
            }
        }
        cnt++;
        next_permutation(b,size);
    }
}
int main(){
    int n;
    int p;
    cin >> n >> p;
    
    int *arr = new int[n];
    
    if(p == 1){
        int next;
        cin >> next;
        problem1(arr,next,n);
    }
    else if(p == 2){
        for(int i = 0; i < n; i++)
            cin >> arr[i];
        problem2(arr,n);
    }
    return 0;
}

구글 검색결과, 팩토리얼을 사용하는 방법이 있었는데

해결법

입력 : 4 1 3

 => 4개의 원소를 가진 순열의 3번째 집합을 구하라

1 2 3 4

1 2 4 3

1 3 2 4

식으로 하나씩 구하면, O(N!)이 뜬다.

반성한다. ㅠㅠㅠ

int SUM = 0, K = 3;        // 지금까지 경우의 수 SUM, 입력된 사전 순 K

이때 1 X X X가 가질 수 있는 경우의 수는 6가지로, 입력 K에 포함하지 않는다.

(K > 3!)?

FALSE 이기 때문에, 첫 번째 원소는 1이다.

마찬가지로 1 2 X X도 적용하면, (사용하지 않은 가장 작은 수 2)

(K > 2!)?

TRUE 이기 때문에, 다음으로 큰 수를 선택한다.

( 이때 SUM += 2!)

1 3 X X는 입력 범위(K=3)에 포함이 될까?

(K > 2*2!)? 

FALSE로 포함되지 않는다, 1 3 X X가 된다.

다시 한번 1 3 X X에서 1 3 2 X가 포함되는지 확인하겠다.

1 3 2 X를 포함하는가?

(K > SUM + 1!)?    (K = 3)

FALSE로 포함하지 않는다.

1 3 2 X => X는 남는 수로 결정

1 3 2 4가 되는 것이다.

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.