[백준] 1655번 가운데를 말해요 c++

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

 

문제접근 및 풀이

- priority_queue를 2개 사용하여서 해결하였다.

- 하나는 내림차순, 하나는 오름차순 큐를 만들어서 원소를 받는다.

- 원소를 받는 과정에서 두 큐의 크기 차이가 1이 넘지 않도록 한다. -> maxq의 크기가 1개더 크거나 두 큐의 크기가 같도록 한다.

- 이렇게 하면 항상 maxq의 top값이 중간값이 되기 때문이다.

 

priority_queue에 숫자들을 넣고 출력하는 과정

- 첫 원소는 maxq에 집어넣는다.

- 들어오는 원소가 maxq의 top값보다 크면 minq에 집어넣고 아니면 maxq에 집어넣는다.

- 원소를 넣는 과정을 마친 후 maxq의 크기와 minq의 크기를 비교하여 위에서 언급한 조건에 만족하지 않는다면 경우에 따라 top원소를 다른 queue에 push하고 pop하는 과정을 진행해준다.

- 이렇게 되면 maxq의 top값이 항상 중간값이므로 이 값을 출력한다.

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define VMAX 1001
#define INF 987654321

using namespace std;

int main(){
  int n; cin >> n;
  int a[100000];
  priority_queue<int> minq, maxq;
  for(int i=0; i<n; i++) scanf("%d", &a[i]);

  for(int i=0; i<n; i++){
    int x = a[i];
    if(maxq.empty()){
      maxq.push(x);
    }else{
      if(x > maxq.top()){
        minq.push(-x);
      }else{
        maxq.push(x);
      }
    }
    
    if(maxq.size() -2 == minq.size()){ // maxq 원소가 2개 더 많으면 옮기기
      minq.push(-maxq.top());
      maxq.pop();
    }
    if(maxq.size() +1 == minq.size()){ // minq 원소가 1개 더 많으면 옮기기
      maxq.push(-minq.top());
      minq.pop();
    }
//무조건 max = min+1 이나 max=min 이 되어야 함
    printf("%d\n", maxq.top()); // 무조건 maxq를 출력하도록 q를 조작하기
  }
}

느낀점

처음에 문제를 본 후 heap이나 queue 2개로 구현가능할 것 같다고 생각이 직관적으로 들었다. 하지만 생각을 더 발전시키지 못했고 결국 힌트를 찾은 후 생각을 완성하게 되었다. 조금만 더 생각을 했다면 혼자힘으로 풀 수 있지 않았을까? 하는 아쉬움이 남았다.