프로그래머스 - 줄 서는 방법 - C++

hansol_Shin·2021년 6월 30일

알고리즘 프로그래머스

Algorithm

목록 보기

10/12

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

문제설명

접근 방법1

n에 대한 제한이 20으로 엄청 관대해보였다. 따라서 시간복잡도를 생각하지 않고 바로 생각나는 next_permutation으로 풀이했다.
next_permutation으로 나올때 마다 카운트하여 k번째 순열이 나올때 그 값을 저장하여 type을 바꿔주어 answer에 저장하였다.
하지만... 시간초과였다. n이 20일 때 20! 이 엄청난 수 일줄 생각못했다.
다른 방법의 힌트를 얻자면 모든 순열을 알 필요 없이 사전 순서로 나열할 때 k 번째 순열만 알 면 된다.

접근 방법2

먼저 vector<int> num 에 1~20을 오름차순으로 넣어둔다.
예제를 보자
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
의 순열로 나열되고 k=5 일 때, 앞자리를 (n-1)! 로 나누면 몇번째 수가 오는지 알 수 있다.
k-1/(n-1)! 는 4/2 = 2 이고 2번째 index에 있는 num 을 answer 에 넣어준다.
여기서 k-1 을 하는 것은 index를 맞추기 위함이다. (이거 생각하는데 오래걸림...)
이후 k 값을 조정해 주어야 하는데 index 값으로 mod 연산하여 나온 값으로 조정해 준다.
3,1,2
3,2,1
첫 연산에 의해 index 가 2인 num[2] 즉, 앞자리가 3인 위의 두 순열로 선택된다.
이후 (n-1)! 로 mod 연산을 하면 남은 순열의 몇 번째 수 인지 알 수있다. 단, mod연산으로 나온 결과가 0이면 (n-1)! 번째 수 이므로 k = (n-1)! 로 설정해준다.
특정 num[i] 을 answer 에 넣어줄 때 num[i] 를 vector에서 삭제해 주면 다음 수를 넣을 때 계산이 편리하다.

코드

#include <string>
#include <vector>
using namespace std;

long long fac(int a){
    long long ans = 1;
    for(int i=1;i<=a;i++){
        ans*=i;
    }
    return ans;
}
vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<int> num;
    long long now=k;
    int cnt=1;
    for(int i=1;i<=20;i++){
        num.push_back(i);
    }
    
    while(cnt != n){
        long long tmp = fac(n-cnt);
        int idx = (now-1) / tmp;
        answer.push_back(num[idx]);
        num.erase(num.begin()+idx);
        cnt++;
        now %= tmp;
		if (now == 0)
			now = tmp;
    }
    answer.push_back(num[0]);
    return answer;
    
}