아래 모든 문제들은 프로그래머스에서 제공 되는 문제를 이용하였습니다, 감사합니다.

• 틀린거 없음!

1. 줄 서는 방법

문제 설명

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

입출력 예

풀이

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

vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<int> value;
    int v_index = 0;
    long long tmp = 0;
    long long max = 0;
    for(int i = 1; i <= n; i++)
            value.push_back(i);
    int i = 0;
    k--;
    
    while(k > 0)
    {
        max = 1;
        for(i = 1; k >= max * (i); i++)
            max *= i;
        for (int j = 0; j < value.size() && v_index < n - i; j++)
            if(value[j] != 0)
            {
                v_index++;
                answer.push_back(value[j]);
                value[j] = 0;
            }
        tmp = 0;
        for (int j = 0; j < value.size(); j++)
        {
            if(value[j] != 0)
            {
                   break;
                }
                tmp++;
            } if(tmp == (k /max))
                {
                    answer.push_back(value[j]);
                    value[j] = 0;
                    v_index++;
                
        }
        k = k % max;
    }
    for(int j = 0; j < value.size(); j++)
        if(value[j] != 0)
            answer.push_back(value[j]);
    return answer;
}

설명

• 문제는 여러 경우의 수 중 k번째에 나오는 조합을 구하는거다.
• dfs를 쓰면 쉽게 모든 조합을 구할수 있겠지만, 최대 경우의 수가 20! 이기 떄문에 10억을 넘어간다. 고로 실행초과가 나온다.
• 그래서 문제를 풀기위해 규칙을 찾아야 했다.
  
• n이 4일때 모든 조합을 나열했다.

• 0번 쨰 인댁스 별로 나누어 보니, 6개씩 나누어 떨어졌다.
• 여기서 6 == (123) 이라는 값과 같았다.
• 자리 수별로 올수 있는 경우의 수를 구한 값과 같았다.

• 아랫 자릿수도 같은 식으로 규칙이 나누어 떨어졌다.

• 마지막 자리수는 올 수 있는 경우의 수가 하나다.
  결론
• 그래서 나는 나눌 수 있는 최대 값을 max값에 넣어 구하고
• 그 값을 그 값으로 나누어 떨어지는 몫으로 자리 값을 구해주었다.
• 그리고 남은 나머지들은 다음 자릿수들을 구하기 위해 넘겨주었다.
• 이 문제를 풀기는 했지만, 설명하려니 매우 복잡하다.
• 짜증나는 문제였다!