Life Engineering
[BOJ 1927] 최소 힙(C++) 본문
https://www.acmicpc.net/problem/1927
1927번: 최소 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
|
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
/* 시간초과 해결해야 */
#include <bits/stdc++.h>
using namespace std;
vector<long> heap;
void insert(int item){
long temp;
heap.push_back(item);
int node=heap.size()-1;
int parent=node/2;
while(true){
if (parent==0 || heap[node]>=heap[parent]){
break;
}
temp=heap[node];
heap[node]=heap[parent];
heap[parent]=temp;
node=parent;
parent=node/2;
}
}
long pop(){
long top, temp;
if (heap.size()==1){
return 0;
}
else{
top=heap[1];
heap[1]=heap.back();
heap.pop_back();
int node=1;
while (true){
int left=node*2;
int right=left+1;
if (left>=heap.size()){
break;
}
long minValue=heap[left];
int minPos=left;
if (right<heap.size() && minValue>heap[right]){
minValue=heap[right];
minPos=right;
}
if (heap[node]>minValue){
temp=heap[node];
heap[node]=heap[minPos];
heap[minPos]=temp;
node=minPos;
} else{
break;
}
}
return top;
}
}
int main(){
int N;
vector<long> items;
vector<long> ress;
long res;
long item;
cin>>N;
heap.push_back(0);
for (int i=0; i<N; i++){
cin>>item;
items.push_back(item);
}
for (int i=0; i<N; i++){
item=items[i];
if (item==0){
res=pop();
ress.push_back(res);
}
else{ //insert
insert(item);
}
}
for (int i=0; i<ress.size(); i++){
cout<<ress[i]<<"\n";
}
}
|
cs |
최소 힙을 구현하는 문제.
배열로 구현함.
pop 할 때 left, right 자식 비교해서 작은 값이 있을 경우 바꿔준다. 인덱스 값도 이동시킴.
'Problem Solving' 카테고리의 다른 글
| [BOJ 9202] Boggle (C++) (0) | 2021.07.22 |
|---|---|
| [BOJ 1202] 보석 도둑(C++) (0) | 2021.07.22 |
| [BOJ 3055] 탈출 (C++) (0) | 2021.07.20 |
| [프로그래머스] 숫자 문자열과 영단어(2021 카카오 인턴십 기출) (0) | 2021.07.15 |
| [프로그래머스] 단어 변환(DFS/BFS) (0) | 2021.07.15 |