boj, 백준) 1655. 가운데를 말해요 ( C / C++)

1. 문제 링크

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

1655번: 가운데를 말해요

2. 문제 개요

동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 말해줬을 때 동생을 1, 1, 2, 2, 2, 2, 5와 같이 그때 불러준값의 중간값을 계속 말해야 한다.

프로그램을 작성하시오.

 

3. 문제 힌트

매번 가운데를 말해야 한다. 전체 크기를 알고 이게 정렬되어있다면 중간 인덱스를 지정하여 바로 출력할 수 있을 것이다. 그런데 이렇게 하기에는 매번(n) 정렬해야 하고(nlogn), 그러면 O(n^2 logn)이 되어 시간 초과가 날 것이다.

 

그러면 매번 중간값을 찾아내지 말고 이전의 중간값을 잘 사용해서 문제를 풀 수는 없을까?

 

답의 범위는 지금 중간값, 중간값보다 하나 작은 값(-1 아님), 중간값보다 하나 큰 값. 이 세 개 중에서 다음의 답이 변경될 것이다.

힙을 잘 사용해보자.

 

4. 문제 풀이

 

힙을 2개 만들자. 최소 힙, 최대 힙.

 

현재 중간값을 기준으로, 왼쪽에는 최대 힙이 있다고 하고, 오른쪽에는 최소 힙이 있다고 가정하자.

오른쪽의 최소 힙에는 cur보다 크다면 push, 왼쪽의 최대 힙에는 cur보다 작다면 push 할 것이다.

1,5,2,0.... 를 기준으로 예를 들어보겠다.

 

초기 상태 1출력

밑의 숫자는 Size의 차라고 하자. 만약에 Max가 Min보다 1개 많다면 1 : 0 이 될 것이다.

 

이제 5가 들어온다면 cur보다 크기 때문에 오른쪽의  Min heap에 들어갈 것이다.

 

 

두번째 상태 1출력

이번엔 짝수이다. 짝수일 경우에는 문제에서 중간의 2개 중 작은 값을 cur로 취하라고 했다. 이 부분을 구현해주자.

짝수인 경우는 두 힙의 차가 1 : 0 이거나 0 : 1일 때다.

따라서 조건문은 저 위의 경우일 때 분기하는 걸로 하고, cur과 top의 값을 비교하고 바꿔야 한다면 cur로 옮겨주고 현재의 cur값은 다른 heap으로 옮겨주도록 하자.

 

다음 2가 들어온다.

 

세번쨰 상태

이처럼 2가 차이나는 경우에는 비교할 것도 없이 중간값을 찾아야 하기 때문에, 현재의 cur을 왼쪽의 Max heap에 옮겨주고 Min의 Top을 cur로 바꿔야 한다.

 

세번째 상태. 출력 2

마지막으로 0이 들어온다면 

네번째 상태

짝수가 되고, (1:0 인 경우) 1 인쪽의, 여기서는 Max heap이다. Max heap의 top과 cur을 비교하여 더 작은 쪽을 cur로 대치하고 현재의 cur을 Max로 넘겨준다.

네번째 상태 1출력

 

중요한 부분은 다 살펴본 것 같다. 이렇게 코드를 구현해주자.

 

5. 코드

#include <cstdio>
#include <queue>
#include <functional>
using namespace std;

priority_queue <int,vector<int>,less<int>> left;	
priority_queue <int, vector<int>, greater<int>> right;	
int n, cur;

int main()
{
	scanf("%d", &n);
	scanf("%d", &cur);
	printf("%d\n", cur);

	for (int i = 2; i <= n; ++i) {
		int val;
		scanf("%d", &val);

		if (cur <= val)
			right.push(val);
		else
			left.push(val);

		if (left.size() - right.size() ==2){
			right.push(cur);
			cur = left.top();
			left.pop();
		}
		else if (right.size() - left.size() == 2){
			left.push(cur);
			cur = right.top();
			right.pop();
		}
		else if (left.size() - right.size() == 1){
				if (left.top() < cur) {
					right.push(cur);
					cur = left.top();
					left.pop();
				}
			}
		else if(right.size() - left.size() == 1){
				if (right.top() < cur) {
					left.push(cur);
					cur = right.top();
					right.pop();
			}
		}
		printf("%d\n", cur);
	}
	return 0;
}

6. 결과 사진

지적 댓글 환영입니다 :)