백준 1655번 가운데를 말해요

- 문제 설명

 

수빈이는 동생에게 '가운데를 말해요' 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

 

 

- 입력

 

첫째 줄에는 수빈이가 외치는 정수의 개수 N (1 <= N <= 100,000)그 다음 N 줄에 걸쳐서 수빈이가 외치는 정수의 개수가 주어진다. (입력되는 정수는 -10,000 보다 크거나 같고, 10,000 보다 작거나 같다.)

 

 

- 출력

 

한 줄에 하나씩 N 줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력

 

 

* 문제 풀이의 핵심

 

1. 우선순위 큐를 2개 사용해야 한다.

 

- 항상 최소값만 리턴, 항상 최대값만 리턴하는 큐 2개를 생성해야 한다.

 

 

2. 로직

 

※ 최대값만 리턴하는 우선순위 큐 : q_max, 최소값만 리턴하는 우선순위 큐 : q_min

 

1) (q_max 의 크기 == q_min 의 크기) 또는 (q_max 의 크기 == q_min 의 크기 + 1) 을 만족해야 한다.

 

2) q_max 의 최대값 > q_min 의 최소값이라면, q_max 의 최대값과 q_min 의 최소값을 swap 한다.

 

 

3. 그림설명

 

ex) 입력이 1,2,3,4,5 일때 중간값 구하기

 

 

 

- 소스코드

 

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int arr[100001];
priority_queue<int, vector<int>, greater<int>> q_min;	// top()은 항상 최솟값
priority_queue<int, vector<int>, less<int>> q_max;	// top()은 항상 최댓값

int main() {
	int N;
	cin >> N;

	int i;
	for (i = 0; i < N; i++) {
		cin >> arr[i];
	}

	q_max.push(arr[0]);
	cout << q_max.top() << "\n";

	for (i = 1; i < N; i++) {
		if (q_max.size() >= q_min.size() + 1) {
			q_min.push(arr[i]);
		}
		else {
			q_max.push(arr[i]);
		}

		if (q_max.top() > q_min.top()) {
			int t1 = q_min.top();
			q_min.pop();

			int t2 = q_max.top();
			q_max.pop();

			q_min.push(t2);
			q_max.push(t1);
		}

		cout << q_max.top() << "\n";
	}
}

 

 

- 문제링크 : https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

 

- 제출한 코드

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요