1722.순열의 순서

이번 문제는 순열의 순서이다.

1722번: 순열의 순서

일단 풀지 못해서 다른사람들의 코드를 참조했다.

그 이유는 시간복잡도 때문이었다. next_permutation이나 prev_permutation을 사용하면

답은 구할 수 있지만 시간 복잡도 때문에 '시간 초과'가 발생한다... 후... 그래서 다른방식으로

분석을 진행해서 풀어야한다. 다른사람의 풀이를 보고 이해하는데도 머리가 나쁜건지 시간이 좀 걸렸다..

 

< Code 설명 >

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

using namespace std;

bool check[21];

int main()
{
    long long fac[21]; // 팩토리얼 값들 저장할 배열
    fac[0] = 1;
    for (int i = 1; i < 21; i++) // n! 값 배열에 넣기
    {
        fac[i] = i * fac[i - 1];
    }
    int n;    //순열의 크기
    cin >> n; //입력받기
    int s;    //소문제 유형 구분을 위한 변수
    cin >> s; //입력받기
    vector<int> ans(n); //찾는 k번째 순열 값이 저장될 vector

    if(s==1){    // 소문제 유형 1일 때
        long long k;    //순열 번호 변수
        cin >> k; // 순열 번호를 입력받음
        
        for(int i=0; i<n; i++){ // 순열 갯수만큼 돌림(팩토리얼과 관련)
            for(int j=1; j<=n; j++){ // 1부터 n까지 돌림(우리가 찾는 순열과 관련)
                if(check[j])  //이미 찾은 수 일 경우
                    continue; // 패쓰!
                if(k>fac[n-i-1])  // 순열번호 k와 팩토리얼 비교
                    k-=fac[n-i-1];// k보다 작은 팩토리얼이면 k에서 빼줌
                    //k보다 작은 팩토리얼 이라는 의미는 찾을 수 를 포함한다는 의미이다.
                    //즉, 1,2,3,4라는 순열에 ex)k<3! 이면 제일 앞 자리는 1이라는
                    //경우의 수안에 순열이 존재한다는 의미이다. k>3!이면 이미 앞자리가
                    //1 일때의 경우의 수는 지났다는 의미가 된다 (* 아래글 참조 *)
                                  
                else{ // 팩토리얼이 k보다 크다면 
                    check[j]=true;
                    // 해당 팩토리얼은 이미 사용함(이보다 큰 팩토리얼이 나올수 없기 때문)
                    
                    ans[i]=j; // 해당 숫자를 찾는 순열값에 저장
                    
                    break;    // 한 자리를 찾았으므로 다음자리를 찾기위해 i값증가
                }
            }
        }
        for(int i=0; i<ans.size();i++) //우리가 찾은 순열 출력
            cout << ans[i] << " ";
        cout << '\n';
    }
    else if(s==2){
        vector<int>cmp(n); // 입력받은 순열이 저장되는 vector
        long long cnt=1;   // 순열의 순서 변수

        for(int i=0; i<n; i++){ // 순열입력
            cin >> cmp[i];
        }

        for(int i=0; i<n; i++){ 
            for(int j=1; j<cmp[i]; j++){ //입력받은 순열까지 검사
                if(check[j])   // 이미 저장되었다면
                    continue;  // 패쓰
                cnt += fac[n-i-1]; //그게 아니라면 순서의 변화가 생겼기다는 의미이므로
                                   //팩토리얼만큼 더해줌 (* 아래글 참조 *)
            }
            check[cmp[i]]=true;    //해당 숫자는 사용되었음을 check 
        }
        cout << cnt; // 순열의 순서 출력
    }
    return 0;
}

 

< 1번 유형의 경우 >

예를 들어 순열이 1,2,3,4 일 경우

우리가 찾는 순열번호 k는 3이고 코드에서는 팩토리얼과 이 k와 비교하고 있다. 

순열의 제일 앞이 1일 경우 뒤에 2,3,4 세 숫자가 3자리를 만들 수 있는 경우의 수는 3! 이다.

(물론 앞이 1이 아닐 경우에도 3!이지만 이 문제에서는 순서대로(순열의 번호) 찾고 있다)

때문에 3!보다 k가 크다는 의미는 앞이 1일때의 탐색이 끝나고 제일 앞자리의 바뀜이 생겼다는 의미가 된다.

그렇게 되면 3! + α 가 되기 때문에 이 경우의 수로 우리는 어느 정도 진행된 것인지 확인할 수 있는 것이다.

 

반대로 3!보다 k가 작다는 의미는 바뀜없이 해당 조합안에 있다는 의미가 된다. 그러므로

k가 어떠한 팩토리얼 보다 작은 경우 그 값이 순열의 요소들로 정해지는 것이고

정한 숫자는 check라는 배열에 true로 지정해준다. 그래서 for문의 j값으로 check 배열을 탐색 후

true인 수는 이미 순열의 요소로 정해진 값이므로 pass하고 위에서의 팩토리얼 조건과 같이

다음 숫자를 찾아가게끔 코드를 구현하면 된다..

 

< 2번 유형의 경우 >

예를 들어 2,3,1,4의 경우로 생각해보자

i를 사용하는 for문에 의해서  for문 j는 cmp[i]일 때까지 탐색을 진행할 것이다.

j는 1부터 시작해서 cmp[0]이니까 2까지 검색을 할 것이다. check된 값이 있으면 패쓰되고

없으면 거기까지의 팩토리얼이 순열의 순서값에 더해진다.

->예를 들어 위의 내용으로 첫 탐색을 확인하면 cmp[0]=2이다. 하지만 check된적이 없기 때문에

바로 cnt += fac[n-i-1]이 진행된다. fac[(n-i-1)]은 fac[3]=6으로 cmp[0]가 2이기 때문에  

(1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2) 6개 다음 (2 x x x )로 시작하는 값이

나오기 때문에 fac[3]을 이용해서 3!(6)을 더해주는 것이다. 그 다음 제일 앞자리는 2로 찾았기 때문에

그리고 탐색 후에는 입력된 순열의 값은 true로 만들어 준다. 또한 다음 검색에서 cmp[1]=3 까지 j를 이용한

for문에서 찾게된다. 1은 check된적이 없으니 지나간 것이기 때문에 (2,1,x,x)에 대한 경우의 수를 cnt에 더해줘야한다.

그러므로 cnt+=fac[2]가 진행되고 for문이 계속 진행되면 3 역시 check가 되고 다음으로 넘어간다. 이걸 계속 반복하면

팩토리얼로 이전 순열을 다더하게 되면서 동시에 자신이 확인한 숫자에 대해서는 check가 진행된다.

마지막으로 cnt 즉, 순열의 순서를 출력해주면 끝난다.

 

 

# 꽤 쉽지 않았던 문제였다. 우선 요즘 자꾸 시간복잡도 문제와 부딪히고 있다.

  하지만 그것보다는 문제를 어떻게 풀지를 잘 생각하는게 중요한 것 같다.

 

참고 :

https://it-earth.tistory.com/115

https://kosaf04pyh.tistory.com/211