[C++]백준 - 1655번 문제

1655번: 가운데를 말해요 (acmicpc.net)

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줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

 

---

 

생각해 볼 점

---

그림으로 보면 쉽습니다.

 

위와 같은 형태로 힙을 2개 구현해 봅시다.

 

짝수개의  수가 존재하면 작은 수를 반환할 것이기 때문에,

 

답은 항상 좌측(최대)힙의 top을 뽑아서 쓸 것입니다.

 

첫 입력을 좌측 힙에 집어넣고, 그 후부터는

 

양쪽 힙의 size를 가지고 시작하여 입력을 받을 것입니다.

 

입력을 받을 때 두 가지 경우의 수가 있는데,

 

1. 왼쪽 힙의 top보다 크다.

 

 

예를 들어 3을 받으면, 1보다 3이 크므로, 오른쪽 힙에 집어넣습니다.

 

2. 왼쪽 힙보다 작다.

 

왼쪽 힙에 집어넣습니다.

 

입력이 끝나면, 확인 작업을 해야합니다.

 

왼쪽 힙과 오른쪽 힙의 size 차이가 많이 난다면, 가운데 값을 정확히 구할 수 없습니다.

 

위와 같이 왼쪽 힙이 오른쪽 힙의 size보다 2 이상 클 경우,

 

위와 같이 왼쪽 힙의 top을 오른쪽 힙에 push 해줍니다.

 

반대로 오른쪽 힙이 왼쪽힙의 size보다 클 경우에도 오른쪽 힙의 top을 왼쪽 힙에 넣어주면 됩니다.

 

코드

---

#include <iostream>
#include <queue>
using namespace std;

int main() 
{
	int N;
	cin >> N;
	priority_queue<int> pq_left;       //맥스 힙, top이 항상 가운데 값임
	priority_queue<int, vector<int>, greater<int>> pq_right;    //최소 힙
	
	
	int input;
	scanf("%d", &input);
	pq_left.push(input);
	
	pair<int, int> size = make_pair(1, 0);  //<왼쪽 size, 우측 size>
	printf("%d\n", input);
	
	for(int i = 1; i < N; i++)
	{
	    int input;
	   scanf("%d", &input);
	    
	    int size_gap = size.first - size.second;
	
	    if(input < pq_left.top())
	    {
	        size_gap++;
	        pq_left.push(input);
	        
	        //왼쪽힙이 너무 많으면 우측 힙으로 옮김
	        if(1 < size_gap || size_gap < 0) 
	        {
	            pq_right.push(pq_left.top());
	            pq_left.pop();
	            size.second++;
	        }
	        else size.first++;
	    }
	    else 
	    {
	        pq_right.push(input);
	        size_gap--;
	        
	        //우측 힙이 너무 많으면 왼쪽 힙으로 옮김
	        if(size_gap != 0) 
	        {
	            pq_left.push(pq_right.top());
	            pq_right.pop();
	            size.first++;
	        }
	        else size.second++;
	    }
	    
	    printf("%d\n", pq_left.top());
	}
	
	return 0;
}

 

그 외

---