[프로그래머스/C++] 줄 서는 방법

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

코딩테스트 연습 - 줄 서는 방법

줄 서는 방법

문제

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

 

풀이

입출력 예시

 

풀이

완전 탐색으로 모든 경우의 수를 나열해서 k 번째의 경우를 찾으려고 하니 시간 초과가 떴다.

 

이 문제는 전체 경우의 수를 구해서 부분 부분을 파고 들어가서 답을 찾아야했다. 그 과정은 아래와 같다.

 

문제의 예시의 경우,1, 2, 3 은 총 6가지 경우의 수가 있다.[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]

 

2번 지날 때 마다 첫번째의 수가 바뀌고 있다. 즉, (3 - 1)! 만큼 지날 때 마다 먼저 오는 수가 바뀌고 있다.

 

문제의 예시에서 k는 5라고 되어있다. k를 위에서 구한 수, (3 - 1)! = 2 로 나누어 본다. 그러면 몫이 2, 나머지가 1이 나왔다. 이는 다르게 말하면 2번째 인덱스에 해당하는 수(위의 경우에는 3)가 먼저 나왔다는 소리다. 만약 나머지가 0이었다면 몫에 -1을 해주어야 이 규칙을 만족할 수 있다. (왜 그런지는 1 ~ 6을 각각 2로 나눠본 뒤. 위의 경우들을 보면 알 수 있다.)

 

나머지가 1이라는 의미는, 가장 첫번째의 경우라는 의미이다. 즉, 첫 번째 수를 제외하고 작은 수 부터 나열되어있다는 소리이다. 반대로 0이 나왔다면, 가장 마지막 경우라는 의미로 첫 번째 수를 제외하고 큰 수부터 나열되어 있다는 뜻이다.둘 다 아니라면 위에서 한 과정을 다시 반복한다.

 

정리하자면,

 

1. k 를 (n - 1)! 로 나눈 몫을 구해 첫 번째에 등장하는 수를 찾는다.

2. 나머지를 보고 다음을 진행한다.

2-1. 나머지가 1이면 남은 수들을 오름차순으로 나열한다.

2-2. 나머지가 0이면 남은 수들을 내림차순으로 나열한다.

2-3. 둘 다 아니라면 k 에 나머지를 저장해 위 과정을 다시 밟는다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long f(int n) {
    long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<int> line;
    
    for (int i = 1; i <= n; i++) {
        line.push_back(i);
    }
    
    while (1) {
        long long result = f(n - 1);
        int a = k / result;
        long long b = k % result;
        
        if (b == 0) {
            a--;
        }
        
        answer.push_back(line[a]);
        line.erase(line.begin() + a);
        
        if (b == 1) {
            for (int i = 0; i < line.size(); i++) {
                answer.push_back(line[i]);
            }
            return answer;
        }
        else if (b == 0) {
            for (int i = line.size() - 1; i >= 0; i--) {
                answer.push_back(line[i]);
            }
            return answer;
        }
        else {
            k = b;
            n--;
        }
    }
    
    return answer;
}