[Baekjoon/백준] 1655번: 가운데를 말해요(C/C++)

단계별로 풀어보기 22단계(이분 탐색) 4번 문제

https://www.acmicpc.net/step/13

우선순위 큐 단계

---

백준 1655번: 가운데를 말해요

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

---

문제 설명

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

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

---

입력과 출력

입력: 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

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

---

접근 방법

이번 문제는 정수 개수 N을 입력받고 N개의 정수를 입력받아서 그 수들의 중간 값을 출력하는 문제다. 만약 정수가 짝수개 있다면, 중간의 두 개의 값 중 작은 값을 출력한다. 예제에 따라서 과정을 설명하면 아래와 같다.

N = 7, 총 7개 입력 가능
1 입력 : [ 1 ]
출력 : 1
5 입력 : [ 1, 5 ] 정수 개수가 짝수이므로 둘 중 작은 값 출력
출력 : 1
2 입력 : [ 1, 2, 5 ]
출력 : 2
10 입력 : [ 1, 2, 5, 10 ] 짝수이므로 중간인 2, 5 중 작은 값 출력
출력 : 2
-99 입력 : [ -99, 1, 2, 5, 10 ]
출력 : 2
7 입력 : [ -99, 1, 2, 5, 7, 10 ] 짝수이므로 중간인 2, 5 중 작은 값 출력
출력 : 2
5 입력 : [ -99, 1, 2, 5, 5, 7, 10 ]
출력 : 5

일단 위 예제 설명을 보면 오름차순 우선순위 큐가 필요할 것이다.

다만 중간의 수를 출력하는 방법이 문제다. 단순히 생각해서 오름차순 우선순위 큐에 push한 후, 현재 큐 크기를 절반으로 나누고 그 몫만큼 top을 pop하고 중간 값을 출력한 뒤, 이전에 pop했던 top 값을 다시 push하는 방법이 있다. 하지만 N의 크기가 크고 문제에서 요구하는 시간 제한이 0.1초라서 이 방법은 시간 초과가 발생할 것이다.

따라서 다른 방법으로 문제를 해결해야한다. 우선 하나의 우선순위 큐 대신, 내림차순, 오름차순으로 두개의 우선순위 큐를 사용해야 한다. 두 큐는 사이즈가 같을 때 내림차순 큐에 넣고, 아니라면 오름차순 큐에 넣는다. 즉, 내림차순 큐에 먼저 넣고 이후 오름차순 큐에 넣는다.

내림차순 큐는 오름차순 큐보다 비교적 작은 값들을 저장하고, 오름차순 큐보다 정수 개수가 하나 더 많거나 같다. 오름차순 큐는 내림차순 큐보다 비교적 큰 값들을 저장한다. 만약 내림차순의 top 값이 오름차순 top값이 더 클 경우에는 top 값을 서로 바꿔준다. 이렇게 하면 내림차순 큐의 top 값이 중간 값이 될 것이다.(짝수의 경우에서도 오름차순 큐보다 더 작은 값을 저장해놓으므로) 이후 내림차순의 top 값을 출력하면 된다. 조금 더 이해를 돕기위해서 예제를 통해 설명하면 아래와 같다.

1 입력 -> 1 출력 : 두 큐 모두 비었으므로 내림차순 큐에 우선적으로 입력
내림차순 큐 [ 1 ]
오름차순 큐 [ ]

5 입력 -> 1 출력 (짝수) : 오름차순 큐에 입력
내림차순 큐 [ 1 ]
오름차순 큐 [ 5 ]

2 입력 -> 2 출력
내림차순 큐 [ 2, 1 ]
오름차순 큐 [ 5 ]

10 입력 -> 2 출력 (짝수)
내림차순 큐 [ 2, 1 ]
오름차순 큐 [ 5, 10 ]

-99 입력 -> 2 출력
내림차순 큐 [ 2, 1, -99 ]
오름차순 큐 [ 5, 10 ]

7 입력 -> 2 출력 (짝수)
내림차순 큐 [ 2, 1, -99 ]
오름차순 큐 [ 5, 7, 10 ]

5 입력 -> 5 출력
내림차순 큐 [ 5, 2, 1, -99 ]
오름차순 큐 [ 5, 7, 10 ]

*같은 경우(5 대신 6 입력)
6 입력 -> 5 출력 : 두 큐의 top 값인 5와 6을 서로 바꿈
내림차순 큐 [ 6, 2, 1, -99 ] => [ 5, 2, 1, -99 ]
오름차순 큐 [ 5, 7, 10 ] => [ 6, 7, 10 ]

참고했던 이 블로그 글을 통해서 그림을 보면 좀 더 쉽게 이해할 수있을 것이다.

---

코드

#include <iostream>
#include <queue>
#include <functional>	//greater
using namespace std;

priority_queue<int> pq1;	//내림차순
priority_queue<int, vector<int>, greater<int>> pq2;	//오름차순

int main(int argc, char * argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N, num, pq1_top, pq2_top;
	cin >> N, num;

	for (int i = 0; i < N; i++) {
		cin >> num;
		
		if (pq1.size() == pq2.size())
			pq1.push(num);
		else
			pq2.push(num);

		if (!pq1.empty() && !pq2.empty() && (pq1.top() > pq2.top())) {
			pq1_top = pq1.top();
			pq2_top = pq2.top();
			pq1.pop();
			pq2.pop();
			pq1.push(pq2_top);
			pq2.push(pq1_top);
		}

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

	return 0;
}

---

결과

백준 제출 결과