티스토리 뷰
728x90
https://www.acmicpc.net/problem/1655
1655번: 가운데를 말해요
첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
우선순위 큐 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
- 토마토
- Swift
- dfs
- 최단경로
- 스택
- 동적계획법
- 최소힙
- 백준
- 정렬
- BFS
- 수학
- 백트래킹
- 다이나믹프로그래밍
- 게임이론
- 그리디알고리즘
- 알고리즘
- c++
- 트리
- 웹크롤링
- 가장 큰 수 프로그래머스
- 브루트포스
- 최대힙
- 이분탐색
- 가장 큰 수 Swift
- 투포인터
- 자바
- 프로그래머스
- 우선순위큐
- 파이썬
- dp
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함