프로그래머스 줄 서는 방법 c++ (구현)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12936

코딩테스트 연습 - 줄 서는 방법

문제 설명

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

---

입출력 예

입출력 예시 설명

입출력 예 #1
문제의 예시와 같습니다.

풀이

`프로그래머스 / 연습문제 / 줄 서는 방법`으로 분류되어 있는 문제이다.

1번부터 n번까지 사람이 있을 때, 이를 순열로 줄 세워 나열하면 자연스레 사전 순으로 나열된다.

처음 풀이는 1부터 n까지 사람을 순열로 줄을 세워 k번째 순열이 나오는 순간 프로그램을 종료했는데,

이 풀이는 O(N!)의 시간 복잡도가 나오기 때문에, 효율성에서 시간 초과가 떴다.

 

이후 로직의 수행 시간을 줄이기 위해 나름의 규칙을 찾았는데,

n이 1일 때 순열은 1!개

1

n이 2일 때 순열은 2!개

1,2

2,1

n이 3일 때 순열은 3!개

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

n이 4일 때 순열은 4!개

1,2,3,4

1,2,4,3

1,3,2,4

1,3,4,2

1,4,2,3

1,4,3,2

2,~~~

3,~~~

4,~~~

위의 결과를 보면,  n이 x일 때  (x-1)!로 k를 나눠보면 순열의 첫 번째 칸부터 구할 수 있다.

즉 n이 4일 때, k가 7이라고 하면,  7 / 3! == 1이므로,

arr[0]=1

arr[1]=2

arr[2]=3

arr[3]=4

인 배열 arr의 1번째 값인 2가 순열의 맨 앞자리에 오는 것을 알 수 있다.

 

순열의 첫 번째 칸이 어떤 수가 오는지 알았으니 나머지 자리에 대한 순열을 찾으면 된다!

이 경우엔 수행 시간이 줄었을까?

n이 20인 경우엔 한자리를 구했으니 나머지 19자리를 정하는 수열은 총 19!개이며,

최악의 경우 19!-1번째 수열을 구해야 하기 때문에 시간 복잡도는

똑같이 O(N!)으로 시간 초과가 뜬다.

 

이제 수열 알고리즘은 과감히 버리고 위에서 찾은 규칙으로 각 자리수를 직접 찾아보자.

n이 4이고 k가 6이라고 하자.

배열은

arr[0]=1

arr[1]=2

arr[2]=3

arr[3]=4

가 된다.

//(n-1)!은 n!/n과 같다.

 

1. 4(n)개의 숫자 중 앞에 올 숫자.

 div  = 6 / (4!/4)  ==1

mod = 6 % (4!/4) ==0

arr의 div번 째 숫자를 순열에 넣고 arr의 div 요소를 제거.

arr[0]=1

arr[1]=3

arr[2]=4

 순열 = {2}

 

2. 3(n-1)개의 숫자 중 앞에 올 숫자.

//위에서 구한 mod를 나누어 준다.

div = 0 / (4!/4/3) ==0

mod = 0 % (4!/4/3) ==0 

arr의 div번 째 숫자를 순열에 넣고 arr의 div 요소를 제거.

arr[0]=3

arr[1]=4

순열 = {2,1}

 

3. 2(n-2)개의 숫자 중 앞에 올 숫자.

//위에서 구한 mod를 나누어 준다.

div = 0 / (4!/4/3/2) ==0

mod = 0 % (4!/4/3/2) ==0 

arr의 div번 째 숫자를 순열에 넣고 arr의 div 요소를 제거.

arr[1]=4

순열 = {2,1,3}

 

4. 마지막 남은 배열의 숫자를 순열에 넣는다.

순열  = {2,1,3,4}

 

이렇게 n이 4이고 k가 6일 때 k번째 순열을 구해 봤는데,

사실 6번째 순열은 1,4,3,2로 정답과 다른 순열이 구해진다.

이유는, k가 나누어 (n-i)!로 나누어떨어질 때 문제가 발생하기 때문이다.

k가 5이고 n이 4일 때 순열의 첫 번째 수는,

5/(4-1)! ==0으로 arr의 0번 째인 숫자인 1이 온다.

k가 6이고 n이 4일 때 순열의 첫 번째 수는,

6/(4-1)! ==1이고 나누어떨어지기 때문에, arr의 0번째 숫자인 1이 와야 하지만, 1번째 숫자인 2가 온다.

그렇기 때문에 처음 k가 주어질 때, 위의 풀이로 k번째 순열을 구하려면 k에 1을 빼줘야 한다. 

코드

#include <string>
#include <vector>

using namespace std;

long long facto(long long num){
    if(num==1)
        return 1;
    return facto(num-1)*num;
}

vector<int> solution(int n, long long k) {
    vector<int> answer,vt;
    for(int i=1; i<=n;i++){
        vt.push_back(i);
    }
    if(k==1)//k가 1인 경우 답은 vt그대로
        return vt;

    k-=1;
    long long pre = facto(n);
    long long mod,div;

    while(vt.size()!=1){
        pre/=n;
        mod = k%pre;
        div = k/pre;
        answer.push_back(vt[div]);
        vt.erase(vt.begin()+div);
        k=mod;
        n--;
    }
    answer.push_back(vt[0]);

    return answer;
}