백준 문제풀이 : (1722) 순열의 순서 - C/C++

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

1722번: 순열의 순서

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	128 MB	Gold 5	조합, 수학, 구현

 

 

문제

 

 

풀이 

소문제 1과 소문제 2로 나뉘어있지만 비슷한 방법으로 풀 수 있다. 무식하게 수열을 생성해 풀이하기에는 시간도 메모리도 부족할 것이라 계산해서 풀어야 한다. 

 

핵심은 i 번째 숫자가 바뀌기 위해서는 (N-i)! 개의 순열을 지나야 한다는 법칙에 있다. 예를 들어 순열 '1 3 2 4'의 경우, 두 번째 숫자가 3이 된 상태이며, 변하기 이전 숫자는 2였을 것이다. 

 

두 번째 숫자가 2였을 '1 2 3 4' 순열에서 두 번째 숫자가 3이 된 '1 3 2 4' 순열이 되기 위해서는 최소 (N-i)! 개의 숫자가, 즉 (4-2)! = 2 개의 숫자를 지났어야 한다는 뜻이다. 실제로 1234, 1243 두 개의 수를 지나야 1324 수열이 된다.  

 

이 법칙을 염두하며 소문제 1부터 풀어보자. 대략적인 풀이 방법은 다음과 같다.

 

1. 변수 및 배열 초기화

- 1부터 N까지의 수가 차례로 담긴 '숫자 배열'을 생성한다. (코드 상에서 vc)

- N!, (N-1)!, (N-2)! ... 1! 의 숫자가 차례로 담긴 '팩토리얼 배열을 생성한다. (코드 상에서 farr)

- 정답을 입력할 배열을 생성한다. (코드 상에서 result)

- k의 값을 입력 받는다.

 

2. 1번째 자리부터 N번째 자리까지 k값을 검사하며 알맞는 수를 result 배열에 넣는다.

1-1) farr[i+1] 이 k보다 크거나 같으면 아직 i번째 자리의 수는 바뀌지 않았다는 뜻이다. 따라서 숫자 배열에서 첫번째 수를 꺼내 result 배열에 넣는다. 이후 첫 번째 수는 사용했으므로 숫자 배열에서 삭제해준다.

*이처럼, 사용한 숫자는 숫자 배열에서 삭제하고 있기 때문에, 1-1에서 result 배열에 넣는 숫자 배열의 값은 항상 첫번째 수가 된다.

1-2) farr[i+1] 이 k보다 작다면 i번째 자리의 수가 바뀌었다는 뜻이다. 따라서 몇 번 바뀌었는지를 계산한다. 이후 숫자 배열에서 (바뀐 수+1) 번째 수가 현재 수이므로 해당 수를 result 배열에 넣어준다. (마찬가지로 사용한 수는 숫자 배열에서 삭제한다.)

2) 위 1번 작업 반복이 끝나면 결과를 출력한다. 

 

소문제 2에서도 마찬가지로 i번째 수가 몇 번 바뀌었는지를 계산해서 풀이한다. 자세한 풀이 과정은 코드에서 주석으로 설명했다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long result[21]; //순열을 담는 배열
long long farr[21]; //자릿수별 팩토리얼을 미리 계산해서 저장하는 배열.
// N이 4라면 4자리. {24(4!), 6(3!), 2(2!), 1(1!)} 이 된다.
// 자릿수별로 n!, (n-1)! ... 이 되는 이유는,
// { 4번 자리, 3번 자리, 2번 자리, 1번 자리 } 로 인덱스를 매길 경우,
// 4번 자리의 수가 바뀌기 위해서는 3번 자리까지의 경우의 수 만큼의 수열을 지나야하기 때문이다.

void answer1(int N) { //소문제 1을 해결
    long long k; //
    scanf("%ld", &k);
    
    vector<long long> vc; 
    //1부터 N까지의 수를 차례로 넣을 숫자 배열. 해당 배열에서 조건에 맞는 수를 꺼내 result에 입력한다.
    vc.push_back(0); //값과 배열 인덱스를 일치시키기 위해, 맨 0번째를 0으로 채운다.
    for (long long i=1, num=1 ; i<=N ; i++, num*=i) {
        vc.push_back(i); 
        farr[N-i+1] = num; //팩토리얼 정보를 저장한다. 
    }

    for (int i=1 ; i<N ; i++) { //1번째부터 N번째 인덱스까지 순서대로 수를 채운다.
        if (farr[i+1]>=k) { // 팩토리얼 배열의 다음 수가 k보다 크면 숫자 배열의 첫번째 수를 그대로 넣는다.
            result[i]=vc[1];
            vc.erase(vc.begin()+1); //첫번째 수를 뺐으므로 숫자 배열에서 삭제한다.
        } else {
            int index = 0; 
            for (int j=1 ; farr[i+1]*j<=farr[i] ; j++) { //i번째 수가 몇 번 바뀌었을지를 구하는 부분.
                if (farr[i+1]*j<k) index++;
            }
            result[i] = vc[index+1];
            vc.erase(vc.begin()+index+1);
            
            k%=farr[i+1];
            if (k==0) k=farr[i+1];
        }
    }

    result[N]=vc[1]; //마지막 수는 숫자 배열에 남아있는 수를 넣어줌.

    for (int i=1; i<=N ; i++) {
        printf("%ld ", result[i]);
    }
}

void answer2(int N) { //소문제 2
    vector<long long> vc;
    vc.push_back(0);
    for (long long i=1 , num=1; i<=N ; i++, num*=i) {
        scanf("%ld", &result[i]); //이번엔 결과 배열에 입력 값을 넣어준다.
        vc.push_back(i);
        farr[N-i+1] = num; //소문제 1과 마찬가지로 팩토리얼 배열 만들기
    }
    
    long long count=1; //
    for (int i=1 ; i<N ; i++) { 
        //result 배열의 1번째 인덱스부터 검사해서 수열의 요소 수를 더해준다. 
        if (result[i]==vc[1]) { 
            //i번째 요소가 숫자 배열의 첫번째 수라면 더해줄 값이 없음. 
            vc.erase(vc.begin()+1); //숫자 배열에서 검사한 수(첫번째 수)를 빼준다.
            continue;
        } else {
            //i번째 요소가 숫자 배열의 첫번째 뒷쪽 수라면, 앞쪽에 있는 숫자 만큼 farr[i+1]개의 수열을 지났다는 의미.
            int index=0;
            for (int j=1 ; j<vc.size() ; j++) {
                if (vc[j]==result[i]) { 
                    index=j; //i번째 요소가 숫자 배열의 몇 번째 요소인지 체크하여 저장.
                    break;
                }
            }
            vc.erase(vc.begin()+index); //숫자 배열에서 검사한 수 빼주기.
            count+=farr[i+1]*(index-1); 
            //count에 지나온 수열 수를 더해준다.
            //index는 숫자 배열에서 i번째 요소의 위치, index-1은 i번째 요소 앞에 몇 개의 수가 있는 지를 의미한다.
            //따라서 farr[i+1]*(index-1)의 값은, 지나온 수열 수가 된다.
        }
    }
    
    printf("%ld", count); //결과값 출력
    
}

int main() {
    int N, B;
    scanf("%d\n%d", &N, &B);
    
    if (B==1) answer1(N);
    else answer2(N);
}

 

 

END.