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

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

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

조합의 속성을 파악하는 문제였습니다.

 

풀이방법

 n이 최대 20까지이므로 모든 조합을 backtracking을 사용한다거나 next_permutation내장함수를 사용하게 되면 시간초과가 나게 됩니다. 이를 해결하기 위해서는 n과 k의 특정한 규칙을 찾아야 합니다.

 

나와 있는 예시로 설명하겠습니다. 

n은 3일 때 나올 수 있는 조합의 수는 3!이므로 6개입니다.

k = 1 일 때 answer는 [1, 2, 3]

k = 2 일 때 answer는 [1, 3, 2]

k = 3 일 때 answer는 [2, 1, 3]

k = 4 일 때 answer는 [2, 3, 1]

k = 5 일 때 answer는 [3, 1, 2]

k = 6 일 때 answer는 [3, 2, 1]

 

특정한 규칙을 발견할 수 있습니다.

가장 왼쪽 수가 1씩 증가할 때마다 (n-i)!씩 k가 증가함을 알 수 있습니다. 이를 코드로 구현합니다.

 

가장 왼쪽자리부터 현재 자리 수 i는 j라는 수를 가집니다. j수를 확인하고 넘어갈때는 (n-i)!씩 더해주면서 k이상이 될 때 j를 answer에 push_back 해주고 k를 k - 더해준 값으로 갱신해줍니다. 

 

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll fact(int num){
    ll sum = 1;
    for(int i = 2; i <= num; i++) sum *= i;
    return sum;
}

vector<int> solution(int n, ll k) {
    vector<int> answer;
    vector <int> ck(n + 1);
    
    for(int i = 1; i <= n; i++){
        ll cnt = 0;
        for(int j = 1; j <= n; j++){
            if(!ck[j] && cnt + fact(n - i) < k) cnt += fact(n - i);
            else{
                if(!ck[j]){ 
                    k -= cnt; 
                    ck[j] = 1;
                    answer.push_back(j); 
                    break;
                }
            }
        }
    }
    return answer;
}

 

Test Case

몇 가지 케이스를 작성해보았습니다.

 

input

3, 2

답 : [1,3,2]

 

input

20, 29384857229381

답 : [1 2 3 5 11 13 4 20 6 15 19 7 18 10 12 17 8 16 9 14]