이번엔 백준 골드 2 가운데를 말해요 문제이다.
골드 2 씩이나 되는 문제는 처음 풀어보는데, 문제가 짧아서 골랐다.
문제는 굉장히 간단하다.
계속 들어오는 입력에 대해 매번 중간값을 말해주면 된다.
정수는 최대 10만개 까지 입력받을 수 있으며, 각각 +-10000의 범위를 갖는다.
사실 문제는 간단하지만, 시간 복잡도 관리가 매우 어려워 보인다.
단순히 정렬해서 가운데를 뽑으면 되는 거 아닌가요? 생각할 수 있지만,
정렬 자체가 시간 복잡도가 꽤 있는 알고리즘이기 때문에 위험하다.
최소 힙
직접 정렬을 매번하기 보단 자료구조를 이용해보기로 했다.
우선순위 큐는 최소 힙 구조로, O(NlogN) 만에 정렬이 가능하다.
우선순위 큐를 어떻게 잘 이용해서 한 번 문제를 풀어보려고 한다.
우선순위 큐에서 중간 값을 어떻게 찾을 수 있을까?
구조 자체는 큐이기 때문에 중간 값을 단순히 찾으려면 pop()을 해야한다.
하지만 이 행위 자체가 내용물이 많아지면 시간이 꽤 많이 걸릴 것 같다.
10만개의 수가 있다고 치면 5만개를 pop() 해야하는 것인데, 위험해 보인다.
만약 두 개의 우선 순위 큐를 사용한다면 어떨까?
하나는 최대 힙 하나는 최소 힙으로 두고 둘을 왔다갔다 한다면?
이 아이디어로 계속 고민을 해보자.
계속 고민을 하며 구현을 했지만, 너무 많은 분기에 코드가 지저분해졌다.
뭔가 고려해야 할 조건이 많은 것 같은데 확실하게 논리가 잡히지 않았다.
결국 다른 사람들의 풀이를 참고하기로 했다.
풀이를 대강 살펴보니, 핵심 논리는 아래와 같았다.
- 짝수개일 때, 더 작은 쪽이 중간값이 된다.
- 홀수개일 때 최소 힙 쪽으로 값을 넣으면 된다.
- 잘못 들어간 수라면, 최대 힙과 자리를 바꾸기만 하면 된다.
- 이 때, 잘못 들어갔다는 것은 최대 힙 > 최소 힙인 경우를 말한다.
- 어차피 작은 수 중 최대인 값이 중간값이 될 것이기 때문이다.
- 홀수개일 때, 가운데 값이 된다.
- 짝수개일 때, 최대 힙 쪽으로 값을 넣으면 된다.
- 이 때도 잘못 들어갔다면 자리를 바꾸기만 하면 된다.
- 그럼 자연스럽게 최대 힙의 머리가 중간 값이 된다!
- 결국 작은 수 중 가장 큰 값과 큰 수 중 가장 작은 값을 줄타기 하는 것이다.
최종 구현 코드는 아래와 같다.
cin >> num;
for(int i = 0; i < num; i++){
cin >> digit;
if (max_heap.size() == min_heap.size())
max_heap.push(digit);
// 두 큐의 크기가 같다는 것은 짝수개라는 의미.
else
min_heap.push(digit);
if (!max_heap.empty() && !min_heap.empty()) {
// 두 큐가 비어있지 않고 (처음 2단계가 아님을 의미)
if (max_heap.top() > min_heap.top()) {
// 작은 것들 중 가장 큰 값 > 큰 것들 중 가장 작은 값
int max_val = max_heap.top(), min_val = min_heap.top();
// 이는 둘의 위치가 바뀌어야 함을 의미한다.
max_heap.pop(); min_heap.pop();
max_heap.push(min_val); min_heap.push(max_val);
}
}
cout << max_heap.top() << '\n';
}아이디어를 생각해내는 것은 좋았으나, 자세한 논리가 부족했다.
직관은 분명 개발자에게 중요한 감각이라고 생각한다.
하지만 자신이 직관적으로 느낀 것을 구체화하는 것 또한 중요하다.
구체화하는 실력을 늘리려면, 구현 문제를 많이 풀어봐야 할 것 같다.