프로그래머스] C++ 연습문제 - 줄 서는 방법(level 3)

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

https://programmers.co.kr/learn/courses/30/lessons/12936#

1.문제

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! 이하의 자연수 입니다.

---

입출력 예

n	k	result
3	5	[3,1,2]

입출력 예시 설명

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

2. 조건

1. 자연수 20이하 n이 주어진다.

2. 1 ~ n 까지의 숫자를 차례대로 정렬한다. (n = 5,  1 2 3 4 5)

3. 1 ~ n 까지 순열을 오름차순으로 나열했을 때 k번째의 순열을 구하여라.

3. 풀이

해당 문제는 패턴이 존제합니다.

1 ~ 3 은 총 6가지의 수로 표현이 가능.

1 ~ 4 는 총 24가지의 수로 표현이 가능.

1 ~ 5 는 총 120가지의 수로 표현이 가능.

.

.

.

1 ~ n 은 총 !n 가지의 수로 표현이 가능.

즉, !n 으로 순열의 가지 수를 알 수 있습니다.

그럼 앞자리 숫자를 구하는 방법은?

예를들어 n = 4, k = 5로 가정해 본다면

맨 앞자리엔 1, 2, 3, 4 중 하나가 올 수 있습니다.

그럼 !4는 24이니 24 / 4를 한다면 6이 됩니다.

그렇다면 앞자리가 1일때 6가지, 2일때 6가지, 3일때 6가지, 4일때 6가지를 표현할 수 있다는 소리가 됩니다.

k는 5이니 앞자리는 1일꺼라고 유추해 볼 수 있습니다.

왜?? 오름차순으로 순열이 정렬이 되었으니 6단위로 앞자리가 바뀌니 말이죠.

1. [1234] 7. [2134]

2. [1243] 8. [2143]

3. [1324] 9. [2314]

4. [1342] 10. [2341]

5. [1423] 11. [2413]

6. [1432] 12. [2431]

실제로 5번째 앞자리를 보면 1인걸 확인할 수 있습니다.

앞자리를 구했으니 3개가 남았습니다.(2, 3, 4 말이죠)

2, 3 4 로 만들 수 있는 경우의 수는??

!3으로 표현이 가능해집니다.

이걸로 확인해 볼 수 있는 사실은 다음과 같습니다.

n = 4 라면

(!4, (!3, (!2, (!1))))로 된다는 뜻이 됩니다.

앞자리 수를 구했으면? 다음은 n-1의 팩토리얼을 구한 후 똑같은 방식으로 다시 앞자리를 구하고...

또 n-1의 팩토리얼을 구하고.... 반복..... 

바로.... 재귀로 풀 수 있습니다.!!

다시말해서 n = 4, k = 5일 때 5번째 수를 구하는 공식은 다음과 같습니다. 

(k는 1을 빼줘야 하는데 아래에 그 이유를 설명하겠습니다.)

1. !4 / 4 = 6. (4가지 숫자일 경우 6개단위로 앞자리가 바뀌는 것을 확인)

2. 5 / 6 = 0. (0번째 숫자가 맨 앞으로 옴 = 1) (여기서 5는 k를 뜻함)

3. 5 % 6 = 5이니 다음 나눌 수는 5가됨.

4. n - 1 = 3 (앞자리를 구했으니 !(n-1)를 구해줘야 한다.)

현재 1이 빠지고 [ , 2, 3, 4]가 되었으므로 빈자리를 채워주게 되면 [2, 3, 4]가 된다.

5. !3 / 3 = 2 (3가지 숫자일 경우 2개단위로 앞자리가 바뀜)

6. 5 / 2 = 2(2번째 숫자가 맨 앞으로 옴 = 4) [2, 3, 4]중에 0부터 시작한다면 2번째가 4가 된다.

7. 5 % 2 = 1이니 다음 나눌 수는 1이 됨.

8. n - 1 = 2(3가지 숫자중 앞자리를 구했으니 !(n-1)을 구해줘야 한다.)

현재 1, 4가 빠지고 [ , , 2, 3]이 되었으므로 빈자리를 채워주면 [2, 3]이 된다.

9. !2 / 2 = 1(2가지 숫자일 경우 1개단위로 앞자리가 바뀐다.)

10. 1 / 1 = 1

여기서 k - 1을 안한 문제가 발생합니다.

1은 [2, 3]중 3을 가르키게 되므로 결과 값이 1, 4, 3, 2 가 나오게 되기 때문입니다.

문제에서 k는 !n이하의 자연수라고 했습니다. 즉, k = 24가 될 수 있다는 뜻입니다.

24가 되버리면 6으로 나눴을 때 나누어 떨어지게 되면서 4를 반환합니다.

여기 문제에선 1부터 구한것이아닌 0번 ~ 3번까지를 구하게 되므로 4가 나와버려선 안됩니다.

때문에 k - 1을 해줌으로써 0부터 23까지 의 계산을 할 수 있도록 해줍니다.

10. 1 - 1 = 0

0 / 1 = 0(0번째 숫자가 2이므로 2를 앞으로 빼줌)

현재 남아있는 수는 3이므로 3도 앞으로 빼줌.

11. 결과 [1, 4, 2, 3]

이걸 코드로 옮기면 다음과 같습니다.

4. 코드

#include <string>

#include <vector>

using namespace std;

int fact_n(int n){

    if(n == 1) return n;

    return n * fact_n(n - 1);

}

void fnc(vector<int>& answer, vector<int>& number, long long k, long long n_1, int n){

    if(number.size() == 1) return;

    long long quo = k / n_1;  //2

    long long rem = k % n_1;  //rem = k

    n_1 /= n;   //n_1 = n_1, n = n - 1;

    answer.emplace_back(number[quo]);

    number.erase(number.begin() + quo);

    fnc(answer, number, rem, n_1, n - 1);

}

vector<int> solution(int n, long long k) {

    vector<int> answer, number;

    long long n_1 = fact_n(n - 1);

    for(int i = 0; i < n; i++) number.emplace_back(i + 1);

    fnc(answer, number, k - 1, n_1, n - 1);

    answer.emplace_back(number[0]);

    return answer;

}

여기서 유의해야할 점은 long long입니다.

!20은 조 단위가 넘어가 버림으로 int로 선언했다간 메모리 덤프가 일어나게 됩니다.