1655번: 가운데를 말해요
첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
1. 풀이방법
- 직관적인 풀이 : 중간값을 의미를 떠올리면 수빈이가 숫자를 하나 외칠 때 마다 정렬을 수행 후 중간에 위치한
값을 뽑아내면 된다 . ---> 시간초과 (아마? 작성해서 제출해보진 않았습니다.)
- 우선순위 큐를 이용했습니다.
(1단계)
-가장 큰 값을 뽑아내는 pqless와 가장 작은 값을 뽑아내는 pqgreater를 선언 후
- 매 단계 마다, 그 전의 중간값을 기준으로 pqless에 넣을지 pqgreater에 넣을지를 판단해서 우선순위 큐에 삽입
(2단계)
- 중간값을 뽑아내기 위해서는 한쪽 우선순위 큐만 너무 커져 버리면 안됩니다 즉 데이터의 수가 1차이 이하로 나야
하므로 2이상 차이가 날경우 큰 쪽의 우선순위 큐의 값을 작은 크기의 우선순위 큐 로 옮겨주는 작업을 수행
(3단계)
- 중간값을 뽑아내서 출력 (다음단계를 위한 중간값 저장)
- 문제 조건에 따라서 두 우선순위큐의 사이즈를 비교한후 (편의상) 왼쪽 위에 뽑아낼지 오른쪽 위에서 뽑아낼지
결정하면 됩니다.
2. 주의사항
- 개인적으로는 우선순위 큐 두개를 사용해야 겠다 라는 생각이 든 이후 부터는 상대적으로 매우 쉬웠습니다.
- 문제 조건에 따른 단계별 구현만 차근차근 해주시면 되겠습니다.
3. 나의코드
#include<iostream>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N;
int centervalue;
priority_queue<int, vector<int>> pqless;
priority_queue<int, vector<int>, greater<int>> pqgreater;
void InputToQueue(int num) {
if (num <= centervalue) { pqless.push(num); }
else { pqgreater.push(num); }
}
void ModifyQueue() {
if (pqless.size() > pqgreater.size() + 1) { //2이상 차이날 경우
int modinum = pqless.top();
pqless.pop();
pqgreater.push(modinum);
}
else if (pqgreater.size() > pqless.size() + 1) { //2이상 차이날 경우
int modinum = pqgreater.top();
pqgreater.pop();
pqless.push(modinum);
}
}
void GetCenterValue() {
if (pqless.size() >= pqgreater.size()) {
centervalue = pqless.top();
}
else {
centervalue = pqgreater.top();
}
cout << centervalue << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
int tmp;
for (int i = 0; i < N; i++) {
cin >> tmp;
if (i == 0) {
pqless.push(tmp); centervalue = tmp; cout << centervalue << "\n"; continue;
}
InputToQueue(tmp);
ModifyQueue();
GetCenterValue();
}
return 0;
}'알고리즘 문제풀이 > 큐' 카테고리의 다른 글
| 백준 1715 [C++] (0) | 2020.10.25 |
|---|---|
| 백준 1966 (0) | 2020.02.02 |
