[백준/C++] 1927번 최소 힙
2021. 3. 11. 17:15ㆍ알고리즘/구현
728x90
반응형
문제: www.acmicpc.net/problem/1927
1927번: 최소 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
문제풀이
최소 힙의 구현 문제이다.
C++ STL을 이용하면 쉽게 풀 수 있다.
코드(직접 구현)
#include <iostream>
using namespace std;
int rear=0;
int arr[100005];
void push(int);
void pop();
bool empty();
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int N;
cin>>N;
for(int i=0; i<N; i++){
int x;
cin>>x;
if(x != 0){
push(x);
}
else{
pop();
}
}
return 0;
}
void push(int x){
arr[++rear] = x;
int child = rear;
int parent = child/2;
while(parent > 0 && arr[parent] > arr[child]){
swap(arr[parent], arr[child]);
child = parent;
parent = child/2;
}
}
void pop(){
if(empty()){
cout<<0<<"\n";
return;
}
cout<<arr[1]<<"\n";
arr[1] = arr[rear];
rear--;
int parent = 1;
int child = parent*2;
if(child+1 <= rear){
child = (arr[child] < arr[child+1]) ? child:child+1;
}
while(child <= rear && arr[parent] > arr[child]){
swap(arr[parent], arr[child]);
parent = child;
child = child*2;
if(child+1 <= rear){
child = (arr[child] < arr[child+1]) ? child:child+1;
}
}
}
bool empty(){
if(rear == 0){
return true;
}
else{
return false;
}
}
코드(C++ STL)
#include <iostream>
#include <queue>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int N;
cin>>N;
priority_queue<int, vector<int>, greater<int>> pq; //우선순위 큐(오름차순)
for(int i=0; i<N; i++){
int x;
cin>>x;
if(x != 0){ //입력값이 0이 아니면 push
pq.push(x);
}
else{ //입력값이 0이고
if(!pq.empty()){ //큐가 비어있지 않다면 pop
cout<<pq.top()<<"\n";
pq.pop();
}
else{ //큐가 비어있다면 0 출력
cout<<0<<"\n";
}
}
}
return 0;
}
결과
728x90
반응형
'알고리즘 > 구현' 카테고리의 다른 글
[백준/C++] 2493번 탑 (0) | 2021.03.20 |
---|---|
[백준/C++] 5397번 키로거 (0) | 2021.03.19 |
[백준/C++] 18870번 좌표 압축 (0) | 2021.02.26 |
[백준/C++] 11279번 최대 힙 (0) | 2021.02.25 |
[백준/C++] 5525번 IOIOI (0) | 2021.02.25 |