[프로그래머스] 줄 서는 방법 - 순열(DFS), DP

프로그래머스 - Level 2

 

 

문제

 

풀이 1. 깊이탐색 - 순열 (효율성 통과  X)

#include <string>
#include <vector>

using namespace std;

vector<bool> visited;
long long count = 0;
string answer;


//순열
void dfs(string s,int n, long long k){
    
    if(s.size() == n){
        count ++;
        if(count == k){
            answer = s;
        }   
        return;
    }
    
    for(int i=0; i<n; i++){
        if(!visited[i]){
            visited[i] = true;
            string str = s + to_string(i+1);
            dfs(str,n,k);
            visited[i] = false;
        }
    }
}

vector<int> solution(int n, long long k) {
    
    visited.assign(n, false);
    vector<int> v;
    dfs("", n, k);
    
    for(char c : answer){
        v.push_back(c-'0');
    }
    
    return v;
}

dfs를 활용해 찾고자 하는 순서까지 모든 순열의 경우의 수를 구하였다.

위의 풀이는 시간복잡도가 O(n!)으로  n이 20일 경우 최대 20! 의 순열을 구해야 하기 때문에

효율성면에서 좋지 못했다.

 

풀이2. dp - 규칙

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

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

//팩토리얼 재귀함수로 구현
long long facto(long long num){
    if(num == 1) return 1;
    return num * facto(num-1);
}

vector<int> solution(int n, long long k) {
    
    vector<int> answer;
    vector<int> number;
    for(int i=1; i<= n; i++){
        number.push_back(i);
    }
    
    k-=1;
    long long f = facto(n);
    long long div , mod ; 
    
    while(n > 0){
        f/=n;
        div = k/f;
        mod = k%f;
        answer.push_back(number[div]);
        number.erase(number.begin()+div);
        k=mod;
        n--;
    }
    
    return answer;
}

두 번째 방법은 규칙을 찾아 풀이하는 방법이다. 

 

n개의 숫자를 조합허여 만들어지는 수열의 개수는 n! 개다.

n=3일 경우

{1,2,3}

{1,3,2}

{2,1,3}

{2,3,1}

{3,1,2}

{3,2,1}

6 = 3!

 

수열의 맨 앞자리는 k를 (n-1)!로 나누어 구할 수 있다. 

{1,2,3} = 1

{1,3,2} = 2

{2,1,3} = 3

{2,3,1} = 4

{3,1,2} = 5 

{3,2,1} = 6

 

number = [1, 2, ..., n]

이때 5번째 순열의 맨 첫 번째 수는 

5/(3-1)! = 2

number[3] = 3 으로 3임을 알 수 있다.

이와 같은 방법을 활용하여 모든 숫자를 구할 수 있다.

 

n=3, k=5 라고 가정하자. 

1. 3! 개의 순열 중 5번째 순열의 맨 앞에 올 숫자

div = k / (n-1!) = k / n!/n = 5/3!/3 = 2

mod = k % (n-1!) = k % (n!/n) = 5%(3!/3) = 1

number의 div번째 숫자를 answer 벡터에 넣고, number에서 해당 값 제거

answer = {3}

number = {1, 2}

 

나머지 순열을 구하기 위해 k를 mod로 변경한다. 

k = mod

 

1. 2! 개의 순열 중 맨 앞에 올 숫자.

div = 1/3!/2 = 0

mod = 1%(3!/2) = 1

number의 div번째 숫자를 answer 벡터에 넣고, number에서 해당 값 제거

answer = {3, 1}

number = {2}

 

3. 1! 개의 순열 중 맨 앞에 올 숫자.

div = 1/3!/2/1 = 0

mod = 1%(3!/2/1) = 1

number의 div번째 숫자를 answer 벡터에 넣고, number에서 해당 값 제거

answer = {3, 1, 2}

number = {}

number의 크기가 0이 되면 반복문을 종료한다. 

 

이는 마지막 남은 숫자를 answer 에 추가하는 것과 같다. 

 

그러나 이 풀이는 k가 맨 처음 (n-i)!로 나누어 떨어질 때 문제가 생긴다.

n=3일때의 4번째 순열은 {2,3,1}로, 앞자리가 2 이지만

k/(n-1)! = 4/3!/3 = 2 이 되어

number[2]의 값인 3이 맨 첫번째 자리가 된다.

이를 위해 맨 처음 k에 -1 을 해주는 작업이 필요하다.