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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

문제를 처음 봤을 때, C++ 기준으로 next_permutation()을 사용해서 해결할 수 있을 것이라 생각했지만, n이 20이하의 자연수이므로 효율성 테스트를 통과할 수 없다. 해당 문제는 k번째 방법만 알면 되기 때문에 순열의 모든 경우를 구할 필요 없이 해당 경우만 구해주면 된다. k번째 방법은 첫번째 자리 숫자부터 어떤 숫자가 들어갈지 계산을 통해 구할 수 있다.

예를 들어 n이 5이고, k가 107이라고 해보자. 우선 n이 5이므로 줄 서는 방법은 총 5! = 120 가지가 된다. 총 120가지의 방법이라는 것은 [1, 2, 3, 4, 5]의 숫자에서 첫번째 자리에 1이 들어갈 때 24가지, 2가 들어갈 때 24, ... , 5가 들어갈 때 24가지가 된다는 말이다. 따라서 계산을 통해서 k가 107일 때 첫번째 자리에 들어갈 숫자를 구할 수 있다. 첫번째 자리가 1부터 시작해서 4가 될 때까지 총 96가지 방법이 나온다. 따라서 24 x 4 < 107 < 24 x 5 이므로 첫번째 자리의 숫자는 5가 들어간다는 것을 알 수 있다. 107 - 96 = 11이므로 다음은 두번째 자리 숫자를 구할 수 있다. 남은 숫자 [1, 2, 3, 4] 중에서 1이 두번째 자리에 들어갈 때 6가지, 2가 들어갈 때 6가지, ... 4가 들어갈 때 6가지이므로, 이번에는 6 x 1 < 11 < 6 x 2로 두번째 자리는 2가 들어간다는 것을 알 수 있다. 다음과 같은 방식으로 모든 자리를 구하면 n이 5이고, k가 107일 때의 방법은 [5, 2, 4, 1, 3]이 됨을 알 수 있다. 따라서 다음과 같은 방식으로 구현해주면 해결할 수 있다.

코드

C++

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

long long factorial[21];

void pre_calc() {
    factorial[0] = 1;
    for (int i = 1; i <= 20; i++)
        factorial[i] = factorial[i - 1] * i;
}

vector<int> solution(int n, long long k) {
    pre_calc();
    vector<bool> chk(n, false);
    vector<int> answer;
    int select = 0;
    while (answer.size() != n) {
        for (int i = 0; i < n; i++) {
            if (chk[i]) continue;
            long long num = factorial[n - 1 - select];
            if (k > num) {
                k -= num;
                continue;
            }
            select++;
            answer.push_back(i + 1);
            chk[i] = true;
            break;

        }
    }
    return answer;
}

Java

class Solution {
    long[] factorial = new long[21];

    public void preCalc() {
        factorial[0] = 1;
        for (int i = 1; i <= 20; i++)
            factorial[i] = factorial[i - 1] * i;
    }

    public int[] solution(int n, long k) {
        preCalc();
        int[] answer = new int[n];
        boolean[] check = new boolean[n + 1];
        int select = 0;
        while (select != n) {
            for (int i = 1; i <= n; i++) {
                if (check[i]) continue;
                long num = factorial[n - 1 - select];
                if (k > num) {
                    k -= num;
                    continue;
                }
                check[i] = true;
                answer[select++] = i;
                break;
            }
        }
        return answer;
    }
}