Programmers - 줄 서는 방법

---

title: Programmers - 줄 서는 방법
date: 2022-07-18
tags:

• Algorithm

---

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

문제 요약

1~n번까지의 사람이 줄을 선다. 줄을 서는 방법은 사전 순으로 나열하였을 때의 방법 순서대로 넘버링이 된다.
사람의 수 n과 자연수 k가 주어질 때, k번째 방법을 vector에 넣어 return한다.

문제 풀이

순열 문제이다. 언뜻 보면 처음부터 순열을 확인해가는 것으로 볼 수 있으나, n이 20까지 가능하기에 그 방법은 좋은 방법이 아니다.
20!은 약 2.4e18이다. 무수히 많은 경우의 수를 확인해야 하므로, 규칙성을 찾는 것이 가장 적절하다.
순열의 경우, 앞의 사람이 정해져야 그 뒤에 서는 사람의 순서가 정해진다. 고로 앞에서부터 규칙이 적용된다는 것을 알 수 있다.
3명의 배치 중 2 단위로 1,2,3번이 순서대로 선두에 오게 된다. 4명의 배치라면 6 단위로 순서대로 선두에 온다.
이는 곧 n명의 배치의 경우, n-1! 단위로 선두에 서는 사람이 정해진다는 것이다. 1~n-1! , n-1! + 1 ~ 2 * n-1! ... 순서대로 진행이 된다.
고로 이 값에서 1을 빼준 후, n-1!으로 나누어준 몫이 0부터 n-1까지 나온다.
이는 정확한 절대 위치가 아닌, 남은 인원들 중 상대적인 위치를 의미한다. 고로 vector를 이용하여 각 인원이 빠지는 것을 확인해야 한다.

n-1!을 구하며, 이 과정에서 1~n번까지의 인원을 우선 vector에 넣는다.
이후 k번째 - 1을 Factorial 값으로 나눈 몫에 따라 인원을 배치한다.
여기서, 나눈 후 해당 몫 * Factorial 값만큼 빼주면 남은 인원의 배치를 다시 결정할 수 있다.

2.4e18까지 계산해야 하는 문제를, 최대 20번의 연산 루틴을 통해 해결할 수 있다.
효율성 검사를 포함하여 모든 케이스에서 약 0.01ms의 우수한 성능을 얻을 수 있었다.

프로그램

#include <vector>

using std :: vector ;

vector < int > solution ( int n , long long k )
{
    vector < int > answer ;
    vector < int > vNumberList ;
    long long llFactorial = 1 ;



    for ( int i = 1 ; i < n ; ++i )
    {
        vNumberList.emplace_back ( i ) ;
        llFactorial *= i ;
    }
    vNumberList.emplace_back ( n ) ;

    for ( int i = n - 1 ; i >= 1 ; --i )
    {
        int iIndex = ( k - 1 ) / llFactorial ;
        k -= iIndex * llFactorial ;
        llFactorial /= i ;

        answer.emplace_back ( vNumberList [ iIndex ] ) ;
        vNumberList.erase ( vNumberList.begin () + iIndex ) ;
    }
    answer.emplace_back ( vNumberList [ 0 ] ) ;


    return answer ;
}