백준 1722 순열의 순서

작성일 | In |

Problem : 순열의 순서

유형 : 수학

문제 설명

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.
임의의 순열은 정렬을 할 수 있다. 예를 들어 N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

예제 입력

첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다.

1
2
4
1 3

예제 출력

출력 설명

1
1 3 2 4

해결 전략

그냥 모든 경우를 다 만들어 본다면, 20! 로 TLE가 발생하게 된다.
순열의 특징을 파악하면 된다.

1 3 2 4의 두번째 숫자가 3라는 것은.
두번째 숫자가 1, 2 일떄의 모든 경우의 수가 이미 지나갔다는 이야기가 된다.
하지만 이때 숫자는 중복해서 사용할 수 없으므로, 1 을 제외한다면
2일때의 경우의 수가 지나갔다는 이야기 이므로 1 * 2!의 경우의 수가 지나 갔음을 알 수 있다.

역의 경우에도 동일한다.
1 3 2 4이 몇번째 순열 인지를 알고 싶다면
첫번쨰 숫자가 1의 경우, 0의 경우의 수가 지나갔음을 알 수 있다.
이것은 1보다 작은 숫자가, 0개 있기 때문에, 0 * 3!을 통해 알 수 있다.

주의할 점

  • 초기 순열은 0번 순열이 아니고 1번째 순열이다.
  • factorial 을 구하다가, int 범위를 초과 할 수 있으므로 주의한다.

풀이

입력 받는다.

  • 초기 순열을 입력 받는다.
  • 무슨 문제 인지를 구별한다.

문제에 따라 나누어 해결한다.

k번째 순열을 찾는경우

  • 이전에 몇번의 경우의 수가 등장 했는지를 계산한다.
    • 이전의 경우의 수가 한번도 없다면 0일 것이고, 벡터내0 번째 인덱스 값을 출력하면 된다.
  • 사용된 숫자는 벡터에서 지운다.

순열이 몇 번째인지를 찾는경우

  • 숫자가 vec안에 몇번째 인덱스로 있는지 확인한다.
  • 0 번째에 있다면, 원하는 숫자보다 작은, 사용하지 않은 숫자는 0 개 이다.
  • ` 0 x 순열 위치에 따른 팩토리얼 값` 을 통해 찾아 나간다.
  • 사용된 숫자는 벡터에서 지운다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<int> vec;
int n;

int get_idx(int k) {
    for (int i = 0; i <= (int)vec.size(); ++i) {
        if (k != vec[i])continue;
        vec.erase(vec.begin() + i);
        return i;
    }
    return -1;
}

ll get_fac(int num) {
    ll ret = 1;
    for (ll i = 1; i <= num; ++i) 
        ret *= i;

    return ret;
}

void solve_q2() {
    int k, fac_n = n - 1;
    int idx;
    ll sum = 0;
    for (int i = fac_n; i >= 0; --i) {
        cin >> k;
        idx = get_idx(k);
        sum += idx * get_fac(i);
    }
    cout << sum + 1;
}

void solve_q1() {
    ll k;
    int fac_n = n - 1;
    cin >> k;
    k--;

    for (int i = fac_n; i >= 0; --i) {
        int idx = k / get_fac(i);
        k %= get_fac(i);
        cout << vec[idx] << " ";
        vec.erase(vec.begin() + idx);
    }
}

void input() {
    int quiz;
    cin >> n >> quiz;

    for (int i = 1; i <= n; ++i)   vec.push_back(i);

    if (quiz == 1) solve_q1();
    else solve_q2();
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);

    input();

    return 0;
}

피드백

이 문제도 말로 설명하려니까 굉장히 힘드네요.