티스토리 뷰
728x90
https://www.acmicpc.net/problem/1655
우선순위 큐 C++
하나의 수를 입력할때 마다 저장된 수들 중 중간값을 출력하는 문제
접근방법
최대힙과 최소힙을 모두 사용한다는 아이디어를 얻었다.
정렬된 수열을 반 잘라 앞부분은 최대힙에, 뒷부분은 최소힙에 저장해서
최소힙의 루트노드와 최대힙의 루트노드만 참조하여 중간값을 구하는 것이다.
물론 진짜로 반으로 나눠서 넣으면 안되고 입력받을 때마다 둘 중 한 곳에 push해야한다.
최대힙 루트노드 <= 최소힙 루트노드 이어야하기 때문에
새로운 값을 넣을때는 루트노드와 크기비교를 해야한다.
그리고 두 힙의 크기가 2개 이상 차이나면 안되기 때문에
그럴때마다 많은 쪽 루트노드를 적은쪽으로 옮겨줘야한다.
출력할때는 두 힙의 크기를 비교해서 같으면 최대힙 루트노드를
다르면 큰쪽 루트노드 출력
이 두가지를 항상 만족해야 한다.
1. 최대힙과 최소힙의 크기차이는 같거나 1개차이인 상태가 유지되어야 한다.
2. 최대힙의 루트노드의 값이 최소힙의 루트노드의 값보다 항상 작거나 같아야한다.
소스코드
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
priority_queue<int, vector<int>, greater<>> min_heap;
priority_queue<int, vector<int>, less<>> max_heap;
int N;
cin >> N;
for(int i = 0 ; i < N ; i++){
int n;
cin >> n;
//n input
if(max_heap.empty()){
max_heap.push(n);
}else{
if(n < max_heap.top()){
max_heap.push(n);
}else{
min_heap.push(n);
}
}
if(max_heap.size() - min_heap.size() == 2){
min_heap.push(max_heap.top());
max_heap.pop();
}else if(min_heap.size() - max_heap.size() == 2){
max_heap.push(min_heap.top());
min_heap.pop();
}
//peek
if(max_heap.size() == min_heap.size() || min_heap.size() < max_heap.size()){
cout << max_heap.top() << "\n";
}else if(max_heap.size() < min_heap.size()){
cout << min_heap.top() << "\n";
}
}
return 0;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 2003] 알고리즘 106일차 : 수들의 합 2 (0) | 2021.07.21 |
---|---|
[백준 1806] 알고리즘 105일차 : 부분합 (0) | 2021.07.19 |
[백준 10866] 알고리즘 103일차 : 덱 (0) | 2021.07.09 |
[백준 12015] 알고리즘 102일차 : 가장 긴 증가하는 부분 수열 2 (0) | 2021.07.08 |
[백준 17298] 알고리즘 101일차 : 오큰수 (0) | 2021.07.07 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- dfs
- 파이썬
- dp
- 프로그래머스
- 스위프트
- 자바
- c++
- 큐
- 백트래킹
- 게임이론
- 그리디 알고리즘
- 정렬
- 이분탐색
- 스택
- 웹크롤링
- 백준
- 트리
- 알고리즘
- 우선순위큐
- 최대힙
- 최소힙
- 동적계획법
- 브루트포스
- 투포인터
- BFS
- Swift
- 그리디알고리즘
- 최단경로
- 수학
- 다이나믹프로그래밍
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함