[Programmers] 줄 서는 방법

줄 서는 방법

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

풀이

초기 코드 정확성만 모두 통과
next_permutation() 사용

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

vector<int> v;
vector<int> solution(int n, long long k) {
    long long cnt=1;
    for(int i=1; i<=n; i++)
        v.push_back(i);
    
    do{
        if(cnt==k) return v;
        cnt++;
    }while(next_permutation(v.begin(), v.end()));
    
}

하지만, 20! = 2,432,902,008,176,640,000 이다. O(N)으로 효율성에서 시간초과가 발생한다. 아래 코드는 다른 사람의 풀이이다.

1. 재귀를 이용하여 팩토리얼 함수를 구현한다.
2. v 에는 1~n 사이의 수가 순서대로 담겨 있다.
3. while 문 밖에서 fact(n)을 계산하여 시간을 줄일 수 있다.
4. res은 n!/n = (n-1)! 을 의미한다. 또한, k/res, k mod res, 몫과 나머지를 이용하여 answer을 구할 수 있다.
5. v에 남은 마지막 숫자를 answer에 넣는다.

코드

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

vector<int> v, answer;

long long fact(int n){
    if(n==1 || n==0) return 1;
    return n*fact(n-1);
}

vector<int> solution(int n, long long k) {
    int cnt = n;
    for(int i=1; i<=n; i++)
        v.push_back(i);
    
    k--; // index와 맞추기
    long long res = fact(n);
    while(v.size()>1){ // n-1번 반복
        res /= cnt--;
        int i = k/res;
        answer.push_back(v[i]);
        v.erase(v.begin()+i);
        k %= res;
    }
    answer.push_back(v[0]);
    return answer;
}

정리

팩토리얼 개념과 몫과 나머지를 알아야 한다.
참고