❓문제 설명
문제 : 백준 1655 가운데를 말해요
난이도 : 골드 2
문제 요약
- 백준이가 숫자를 하나씩 외칩니다.
- 동생은 백준이가 지금까지 불러준 숫자들 중에서 중간값을 말해야 합니다.
- 만약, 불러준 숫자의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말합니다.
- 외치는 숫자의 개수는 N (1 이상 10만 이하)
- 주어지는 숫자 (-10000 이상 10000 이하)
- 시간 제한은 0.1초 입니다.
예제에 대해서 예상되는 출력을 같이 알아보겠습니다.
백준이가 외친 수 : 1
지금 까지 말한 숫자들 : { 1 }
동생이 말한 중간값 : 1
백준이가 외친 수 : 5
지금 까지 말한 숫자들 : { 1, 5 }
동생이 말한 중간값 : 1
백준이가 외친 수 : 2
지금 까지 말한 숫자들 : { 1, 2, 5 }
동생이 말한 중간값 : 2
백준이가 외친 수 : 10
지금 까지 말한 숫자들 : { 1, 2, 5, 10 }
동생이 말한 중간값 : 2
백준이가 외친 수 : -99
지금 까지 말한 숫자들 : { -99, 1, 2, 5, 10 }
동생이 말한 중간값 : 2
백준이가 외친 수 : 7
지금 까지 말한 숫자들 : { -99, 1, 2, 5, 7, 10 }
동생이 말한 중간값 : 2
백준이가 외친 수 : 5
지금 까지 말한 숫자들 : { -99, 1, 2, 5, 5, 7, 10 }
동생이 말한 중간값 : 5
🎯문제 해결 방법
비슷한 문제로 백준 2696 중앙값 구하기가 있습니다.
이 문제는 우선순위 큐를 이용해 최소힙과 최대힙 두개를 만들어서 중앙값을 구하는 방법을 사용해야합니다.
최소힙과 최대힙으로 중앙값 구하는 방법
1. 최대힙의 크기는 최소힙의 크기보다 하나 더 크거나 같아야 합니다.
2. 최대힙의 최대 원소는 최소힙의 최소원소보다 작거나 같아야 합니다.
두 가지 규칙을 만족하면서 [1, 2,3 ,4 ,5]가 들어오는 경우를 그림으로 설명해보겠습니다.
-
처음 값은 무조건 최대힙으로 들어가게됩니다. 1번 조건을 보면 최대힙의 크기가 최소힙보다 하나가 더 크거나 같아야하기 때문입니다.
-
이때 중앙값은 1 하나이기 때문에 최대힙의 top인 1이 중앙값이 됩니다.
-
다음 숫자는 최대힙의 크기가 최소힙의 크기보다 하나 더 크거나 같아야하는 1번 조건 때문에 최소힙에 들어가게됩니다.
-
최대힙의 최대 원소가 최소힙의 최소 원소보다 작으므로 2번도 만족합니다. 이때 중앙값은 최대힙의 top인 1이 됩니다.
- 1번 조건을 만족하기 위해 3은 최대힙으로 들어가게 됩니다.
- 2번 조건을 만족하는지 봤는데 이때 최대힙의 최대 원소 3이 최소힙의 최소 원소인 2보다 큰 값이므로 조건을 만족하지 못합니다.
- 2번 조건이 만족하지 않을 때는 최대힙의 top과 최소힙의 top을 swap을 해서 해결합니다.
- 이렇게 되면 1번과 2번 조건을 모두 만족하고 이때 중앙값은 최대힙의 top인 2가 됩니다.
- 4는 1번 조건을 만족하기 위해 최소힙에 들어가게 됩니다.
- 2번 조건도 만족하므로 이때 중앙값은 2가 됩니다.
- 1번 조건을 만족하기 위해 5를 최대힙에 넣었습니다.
- 최대힙의 최대 원소가 5이고 최소힙의 최소 원소가 3으로 2번 조건이 만족하지 않으므로 최대힙의 top과 최소힙의 top을 swap 해서 해결합니다.
- 최소힙으로 옮겨간 5는 최소힙의 성질에 맞게 4 아래로 갔습니다.
- 이때 중앙값은 최대힙의 top인 3이 됩니다.
💻전체 코드
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n;
priority_queue<int> mx;
priority_queue<int, vector<int>, greater<int>> mn;
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i=0; i<n; i++) {
int x;
cin >> x;
if(mx.empty()){
mx.push(x);
}else if(mx.size() == mn.size()) {
mx.push(x);
} else{
mn.push(x);
}
if(!mx.empty() && !mn.empty() && (mx.top() > mn.top())) {
int a = mx.top();
int b = mn.top();
mx.pop();
mn.pop();
mx.push(b);
mn.push(a);
}
cout << mx.top() << '\n';
}
return 0;
}