백준 1071번: 소트 [C++]

작성일 | In
플래티넘 5 플래티넘 5

문제

소트

풀이

아래 알고리즘이 해를 찾을 수 있음을 증명할 수 있습니다.

  1. 출력하지 않은 수의 종류가 2개이고 그 차이가 $1$인 경우에는 큰 것을 먼저 모두 출력한 후 작은 것을 모두 출력하고 알고리즘을 종료한다.
  2. 가능하다면 아직 출력하지 않은 수 중 가장 작은 수를 출력한다. 만약 (마지막으로 출력한 수)$+ 1 =$(아직 출력하지 않은 가장 작은 수)인 경우 두 번째로 작은 수를 하나 출력한 뒤 다시 검사한다.

해당 알고리즘으로 수를 하나 출력했다고 합시다. 1번에 따라 알고리즘이 종료되거나 2번에 따라 가장 작은 수가 출력되어야 합니다. 만약 2번에 따라 가장 작은 수가 출력된 경우 아직 출력하지 않은 수들을 내림차순으로 출력하면 $A_i + 1 \ne A_{i + 1}$이므로 알고리즘이 출력한 $A_1$로 시작하는 해가 존재합니다.

해당 알고리즘으로 $A_1, A_2, \dots, A_i$를 출력했고 이를 접두사로 갖는 해가 존재한다고 합시다. 1번에 따라 출력하고 알고리즘이 종료되거나 2번에 따라 수가 출력됩니다. 즉, $A_k + 1 \ne A_{k + 1}$를 만족하도록 $A_{i + 1}$을 출력할 수 있습니다.

따라서 해당 알고리즘으로 출력한 $A$는 $A_i + 1 \ne A_{i + 1}$을 만족하고 가능한 가장 작은 수부터 출력하므로 사전순으로 가장 앞서는 수열이 됩니다.

코드

std::map을 이용해서 개수를 관리하고 현재 수보다 크면서 제일 작은 수를 $\mathcal{O}(\log N)$에 찾을 수 있도록 구현했습니다.

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
#include <bits/stdc++.h>
using namespace std;

map<int, int> cnt;
vector<int> answer;

int getNext(int x) {
    auto iter = cnt.find(x);
    iter++;

    if (iter == cnt.end())
        return -1;
    return iter->first;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        
        if (not cnt.contains(num))
            cnt[num] = 0;
        cnt[num]++;
    }

    int i = cnt.begin()->first;
    while (true) {
        int j = getNext(i);

        if (cnt.size() == 2 and i + 1 == j) {
            for (int k = 0; k < cnt[j]; k++)
                answer.push_back(j);
            for (int k = 0; k < cnt[i]; k++)
                answer.push_back(i);
            break;
        }

        if (not answer.empty() and answer.back() + 1 == i) {
            answer.push_back(j);
            if (--cnt[j] == 0)
                cnt.erase(j);
        }

        answer.push_back(i);
        if (--cnt[i] == 0) {
            j = getNext(i);
            cnt.erase(i);
            i = j;

            if (i == -1)
                break;
        }
    }

    for (auto num : answer)
        cout << num << ' ';

    return 0;
}

백준 1071번: 소트 [C++]