알고리즘/BAEKJOON

백준 16466번 콘서트

pureworld 2019. 1. 3. 01:37
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
#include <iostream>
#include <queue>
#include<algorithm>
#include<vector>
using namespace std;
 
void push_heap(vector<int> &heap, int value) {
    heap.push_back(value);
    int locate = heap.size()-1;
    if (locate == 0) return;
    while (locate > 0 && heap[(locate - 1) / 2] > heap[locate]) {
        swap(heap[(locate - 1) / 2], heap[locate]);
        locate = (locate - 1) / 2;
    }
}
void pop_heap(vector<int> &heap) {
    if (heap.empty()) return;
    heap[0] = heap.back();
    heap.pop_back();
    int locate = 0;
    while (true) {
        int left = 2 * locate + 1; int right = locate * 2 + 2;
        if (left >= heap.size()) break;
        int next = locate;
        if (heap[next] > heap[left])
            next = left;
        if (right<heap.size()&&heap[next] > heap[right])
            next = right;
        if (next == locate) break;
        swap(heap[locate], heap[next]);
        locate = next;
    }
}
int main(void){
    int n;
    int minimum = 1;
    cin >> n;
    vector<int> arr;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        push_heap(arr, a);
    }
    if (arr.size() == 1 && arr[0] == 1) {
        cout << 1;
        return 0;
    }
    if (arr[0] > 1) {
        cout << 1;
        return 0;
    }
    while (!arr.empty()) {
        int first = arr[0];
        pop_heap(arr);
        int second = arr[0];
        if (first < second - 1) {
            cout << first + 1;
            return 0;
        }
    }
    return 0;
 
}
cs

문제 출처:https://www.acmicpc.net/problem/16466



if (arr.size() == 1 && arr[0] == 1) {

        cout << 1;
        return 0;
    }
    if (arr[0] > 1) {
        cout << 1;
        return 0;
    }

출력할 때 이 부분 예외처리를 안해서 처음에 틀렸습니다라고 나왔네요 ㅠㅠ 

처음 이 문제를 봤을 떄priority queue로 풀 수 있을 거 같은데? 라고 생각했었는데

시간 복잡도에 걸릴 것 같은 느낌이 들어서 그냥 heap구현을 해서 풀어 봤습니다.

그런데 priority queue로도 한 번 나중에 도전해봐야겠습니다.

문제를 푸는 개념자체는 어렵지 않아서 따로 설명하지않겠습니다.


저작자표시 (새창열림)