[알고리즘 풀이 분석] BOJ 1655 가운데를 말해요
우선순위 큐 (힙)을 이용한 알고리즘 문제로 BOJ 의 가운데를 말해요 문제를 포스팅 해 보려 한다!
BOJ 1655 가운데를 말해요
문제 목표
정수가 반복적으로 주어질 때 마다 그동안 입력된 수 들 중 중간 값을 구하여 출력
제한 사항
- 주어지는 정수는 1개 이상 100,000개 이하
- 주어지는 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같음
- 그동안 주어진 정수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 출력
나의 풀이
먼저 단순하게 배열을 이용해 주어지는 수 마다 올바른 자리를 찾아 해당 자리에 넣고, 배열의 index 값을 이용해 중간 값을 출력하는 방법을 생각했지만,
우선순위 큐를 사용하는 문제에 이는 해답이 아닐 것이라 예상하였고, 무엇보다도 시간 복잡도에서 통과 할 수 없을 것이 분명했다.
N개의 정수를 입력받을 때 각 수를 입력 받아 자리를 찾을 때 마다 N, 이를 N개의 정수마다 반복하면 O(N^2) 의 시간 복잡도를 갖게 되고, 힙을 사용하라는 것을 보아 분명 최소한 O(NlogN) 의 시간 복잡도를 만족 시켜야 할 것이었다.
힙을 사용해서 고민해 보았지만,, 결론부터 말하자면 적당한 묘안을 생각해 내지 못했고, 한 포스팅에서 아이디어를 얻어 구현하였다
알고리즘은 다음과 같다
- 주어지는 수들을 절반으로 나누어 작을 쪽은 최대힙, 큰 쪽은 최소 힙으로 관리한다
- 최대힙.size() == 최소힙.size() || 최대힙.size() == 최소힙.size() + 1 로 유지하고
- 중간값은 최대힙.top() 으로 도출한다
- 매번 새로운 정수가 입력되면 이전의 중간값과 비교하여 삽입한다
- 도출되어 있는 중간값보다 작거나 같으면 최대힙에, 크면 최소힙에 삽입한다.
- 이후 조건 2에 맞추어 최대힙.top() 을 최소힙으로 혹은, 최소힙.top()을 최대힙으로 옮겨 새로운 중간 값을 도출한다.
작성코드
#include <iostream>
#include <queue>
#include <vector>
// BOJ 1655 가운데를 말해요, 우선순위 큐 사용, 배열을 절반으로 나누는 것이 핵심!
using namespace std;
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
int getMiddleNumber(int newNumber){
int total = maxHeap.size() + minHeap.size();
int mid = maxHeap.top();
int trans;
if (newNumber <= mid) maxHeap.push(newNumber);
else minHeap.push(newNumber);
if (maxHeap.size() == minHeap.size()+2){
trans = maxHeap.top();
maxHeap.pop();
minHeap.push(trans);
}else if(maxHeap.size() +1 == minHeap.size()){
trans = minHeap.top();
minHeap.pop();
maxHeap.push(trans);
}
return maxHeap.top();
}
int main() {
int N;
cin>>N;
int num;
cin>>num;
vector<int> answer;
maxHeap.push(num);
answer.push_back(maxHeap.top());
for (int i = 0; i < N-1 ; ++i) {
cin>>num;
int mid = getMiddleNumber(num);
answer.push_back(mid);
}
for (int i = 0; i < answer.size(); ++i) {
cout<<answer[i]<<'\n';
}
return 0;
}
100% 내 힘으로 푼 것이 아니기에 잊지 않으려고 일부러 포스팅을 한다!
중간 값을 기준으로 배열을 절반으로 나누고, 최대힙, 최소힙의 특징을 이용하는 것이 핵심!
💡해당 풀이는 다음 자료를 참고하였습니다!
❗️포스팅 관련 문제가 있다면 댓글, 메일로 연락주세요!🙆🏻♀️
Author And Source
이 문제에 관하여([알고리즘 풀이 분석] BOJ 1655 가운데를 말해요), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nnnyeong/알고리즘-풀이-분석-BOJ-1655-가운데를-말해요저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)