문제 설명

정수 수열 a₁, a₂, …, aₙ의 각 원소가 1부터 n 사이의 값을 가지며 중복이 없다면 이를 전체 순열(전체 배열)이라고 부릅니다. 예를 들어, [1,3,2]와 [4,3,2,1]은 모두 전체 순열입니다.

전체 순열들을 정렬할 때 다음과 같은 우선순위 규칙을 따릅니다:

• 길이가 n < m이면 a 수열이 앞섭니다.
• 길이가 n > m이면 b 수열이 앞섭니다.
• 길이가 같으면 사전순으로 비교하여 작은 수열이 앞섭니다.

이 규칙에 따르면:

• 1번째 전체 순열: [1]
• 2번째 전체 순열: [1,2]
• 3번째 전체 순열: [2,1]
• 4번째 전체 순열: [1,2,3]

정수 K가 주어졌을 때, K번째 전체 순열을 출력하는 프로그램을 작성하세요.

입력 형식

• 하나의 정수 K (1 ≤ K ≤ 10¹⁵)

출력 형식

• K번째 전체 순열을 한 줄로 출력합니다.

데이터 범위

• 30%: 1 ≤ K ≤ 1,000
• 60%: 1 ≤ K ≤ 1,000,000
• 100%: 1 ≤ K ≤ 10¹⁵

예제

입력: 5
출력: 1 3 2

해결 전략

1. 수열 길이 결정

길이가 n인 전체 순열의 개수는 n!입니다. 따라서 K를 1!, 2!, 3!, … 순서로 빼면서 수열의 길이를 결정합니다.

unsigned long long fact = 1, sum = 0;
int len = 0;
while (++len) {
    sum += fact * len;
    if (sum > K) {
        K = K - sum + fact * len;
        break;
    }
    fact *= len;
}

2. 각 자리 결정

길이가 len인 수열에서 K번째를 찾습니다. 각 자리마다 사용 가능한 숫자 중에서 몇 번째 숫자를 선택할지 계산합니다.

bool used[10000000] = {false};

void findPerm(int len, unsigned long long fact, unsigned long long K) {
    if (len == 0) return;
    unsigned long long block = fact / len;
    int idx = (K + block - 1) / block;
    
    int num = 0;
    int count = idx;
    while (count > 0) {
        num++;
        if (!used[num]) count--;
    }
    
    cout << num << " ";
    used[num] = true;
    
    unsigned long long nextK = (K % block == 0) ? block : K % block;
    findPerm(len - 1, block, nextK);
}

3. 전체 코드

#include <iostream>
#include <vector>

using namespace std;
typedef unsigned long long ull;

bool used[10000000] = {false};

void findPerm(int len, ull fact, ull K) {
    if (len == 0) return;
    ull block = fact / len;
    int idx = (K + block - 1) / block;
    
    int num = 0;
    int count = idx;
    while (count > 0) {
        num++;
        if (!used[num]) count--;
    }
    
    cout << num << " ";
    used[num] = true;
    
    ull nextK = (K % block == 0) ? block : K % block;
    findPerm(len - 1, block, nextK);
}

int main() {
    ull K;
    cin >> K;
    
    ull fact = 1, sum = 0;
    int len = 0;
    while (++len) {
        sum += fact * len;
        if (sum > K) {
            K = K - sum + fact * len;
            break;
        }
        fact *= len;
    }
    
    findPerm(len, fact, K);
    return 0;
}

시간 복잡도

최악의 경우 O(n²)이며, 여기서 n은 수열의 최대 길이입니다. K ≤ 10¹⁵일 때 n ≤ 15이므로 충분히 빠르게 동작합니다.