[Algorithm] Programmers :: 줄 서는 방법

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

프로그래머스

 
long long factorials[21] = { 0 };
bool visited[21] = { false };
 
vector<int> solution(int n, long long k)
{
    vector<int> answer;
    vector<int> v = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 };
 
    for (int i = 1; i <= n; ++i)
    {
        factorials[i] = 1;
 
        for (int j = i; j >= 1; --j)
        {
            factorials[i] *= j;
        }
    }
 
    int nCount = n;
    long long divideNum = factorials[--nCount];
    long long standardNum = k;
 
    while (answer.size() != n)
    {
        long long a = standardNum / divideNum;
        long long b = standardNum % divideNum;
        divideNum = factorials[--nCount];
 
        if (b == 0) --a;
 
        answer.push_back(v[a]);
        v.erase(v.begin() + a);
 
        if (b == 0)
        {
            for (int i = nCount ; i >= 0; --i)
            {
                answer.push_back(v[i]);
            }
 
            return answer;
        }
        else if (b == 1)
        {
            for (int i = 0; i <= nCount; ++i)
            {
                answer.push_back(v[i]);
            }
 
            return answer;
        }
        else
        {
            standardNum = b;
        }
    }
 
    return answer;
}

규칙 찾으려고 시간 날려먹은 문제.

항상 1시간정도만 기준두고 넘어가면 다른사람풀이 봐야지... 라고 마음먹지만, 조금이라도 희망이 보이면 미련을 못버리고 아까운 시간을 날린다.

 

기본적으로 k를 n-1!으로 나눠서 몫과 나머지를 이용해서 몇번째 숫자인지를 구한다.

 

n = 4, k =16이라면 16을 3!으로 나눌경우 몫과 나머지가 각각 2,4가 나온다.

 

1,2,3,4중 index로 2번째, 즉 3이 맨 앞의 숫자에 해당하게 되고 4는 그대로 다음 반복문의 k로 저장된다.

3은 사용했으니까 삭제해준다. 저렇게 erase로 삭제하거나, visited로 방문체크해서 넘기는 방식으로 해도된다.

근데 그러면 코드가 귀찮게 더 길어지니 그냥 erase로 삭제한다.

 

그리고 이 과정에서 가장 중요한게 있는데, 만약 위 과정을 반복하다가 나머지가 몫이 2, 나머지가 0이 나왔다고 가정한다.

그러면 남은 숫자 중 2번째가 아니라 1번째를 answer에 넣어줘야한다.

왜냐하면 몫이 2, 나머지가 0이라는것은 기존의 방식대로 해석하면 2번째껄 넣은 후, 나머지것들 중 0번째를 구하라는 것인데 0번째라는것은 존재하지 않기때문이다. 

 

즉, 이것은 다르게 해석한다. 몫-1번째꺼의 가장 마지막 수열이라고 해석해야한다.

 

n = 4, k = 6이라고 하자. 

총 경우의 수 4!을 3!으로 나누면 맨 앞자리 각 숫자마다 6개씩 조합이 생긴다.

즉 맨 앞자리숫자가 1인것이 6개, 2인것이 6개, 3인것이 6개, 4인것이 6개씩 생긴다.

딱 봐도 k가 6이니까, 앞자리숫자가 1인것중에서 '가장 마지막 수열' 이라는 것을 알 수 있다.

사전 순이니까 가장 마지막 수열이라하면 나머지 남은 숫자들의 수열들을 내림차순한 값들이라는 걸 알 수 있다.

 

그러면 나머지가 1이라면? 

나머지가 1이라는것은 남은 숫자들의 수열중 가장 첫번째라는 것이다.

즉, 몫2, 나머지 1이라면 기존대로 2번째인덱스값을 answer에 넣는다.

그리고 남은 나머지 숫자들의 수열 중 '첫번째' 수열을 구해야 하는데, 사전순이니까 그냥 오름차순값 그대로 다 넣어버리면 된다.