- 문제 링크
백준 1655번 - 가운데를 말해요
해결 전략
본 문제는 해결 Idea를 찾는 것이 꽤나 Tricky하다. 문제를 처음 보자마자 떠오르는 가장 Naive한 풀이법은 다음과 같을 것이다.
매 입력마다 정렬해서 중간값을 찾을까?
허나, 이는 N이 100,000임을 고려했을 때, 당연히 불가능한 풀이이다. 그러나, 불가능함은 자명하지만, 다음과 같은 사실 역시 자명하다.
본 문제를 해결하기 위해서 '정렬'은 반드시 필요하다.
그렇다면, 가장 빠르고 효율적으로 정렬하는 방법은 무엇인가?
그렇다! Heap을 떠올려볼 수 있다.
여기까지는 PS를 연습해본 이라면 어렵지 않게 도출할 수 있다. 그러나, 문제는 그 다음이다. "Heap을 사용해볼까"라는 생각이 들었을 때, 많은 이들이 다음과 같은 간단한 Idea를 떠올려볼 것이다.
-
무언가 중간 지점을 의미하는 Value를 두고, 그 값을 기준으로 Heap을 구축해볼까?
- Value가 매 입력마다 바뀌기 때문에 결국 Linearity가 추가되고, 시간 초과가 날 것이다.
-
STL Heap을 사용하지 말고, 직접 Heap을 구축한 다음, Tree에서의 높이를 따져서 중간값을 찾아볼까?
- 높이와 원소 개수만으로는 선형 코딩 없이 중간값을 특정하기 어렵다.
~> 위와 같은 아이디어는 자연스럽게 폐기된다.
어떤 Idea가 필요할까?
이때, 획기적인 Idea가 등장한다. Max Heap과 Min Heap을 동시에 두고, 마치 모래시계처럼 구조를 설계한다. Max Heap을 아래로, Min Heap을 위로 두고 말이다.
그 다음, 매 입력마다 항상 Max Heap과 Min Heap의 원소 개수 차이가 1이하가 되도록(Max가 더 많게) 만들어주고, 동시에 항상 Min Heap의 Top 원소가 Max Heap의 Top 원소보다 크도록 만들어준다.
~> 이 Idea를 적용하면, 모래시계 하단의 Max Heap의 Top 원소는 항상 '중간값'을 가리키게 된다. 아래 예시를 보자.
1
5
ㅡㅡㅡㅡㅡㅡㅡ
1
5
ㅡㅡㅡㅡㅡㅡㅡ
2
1
10
5
ㅡㅡㅡㅡㅡㅡㅡ
2
1
10
5
ㅡㅡㅡㅡㅡㅡㅡ
2
1 -99
7 10
5
ㅡㅡㅡㅡㅡㅡㅡ
2
1 -99
7 10
5
ㅡㅡㅡㅡㅡㅡㅡ
5
2 1
-99
마치, 스택을 통해 Sequence를 뒤집을 수 있다는 사실을 처음 깨달았을 때와 같은 수준의 신기함이 느껴질 것이다. 최대 힙과 최소 힙을 함께 이용해 중간값을 특정할 수 있다는 것을 잘 기억하도록 하자.
구현은 위 Idea를 그대로 코드로 옮기면 되는 일이라, 추가적인 설명이 필요 없으리라.
아래는 정답 코드이다.
#include <iostream>
#include <vector>
#include <queue>
// BOJ - 1655 Say Middle
using namespace std;
priority_queue<int> maxheap;
priority_queue<int, vector<int>, greater<int>> minheap;
int main(void) {
int n, num;
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> num;
if (i == 0)
maxheap.push(num);
else if (i == 1) {
if (num > maxheap.top())
minheap.push(num);
else {
minheap.push(maxheap.top());
maxheap.pop();
maxheap.push(num);
}
}
else {
maxheap.push(num);
if (maxheap.top() > minheap.top()) {
maxheap.pop();
minheap.push(num);
if (minheap.size() > maxheap.size()) {
maxheap.push(minheap.top());
minheap.pop();
}
}
if (maxheap.size() - minheap.size() > 1) {
minheap.push(maxheap.top());
maxheap.pop();
}
}
cout << maxheap.top() << '\n';
}
return 0;
}