BOJ 1655 가운데를 말해요

 

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

1655번: 가운데를 말해요

 

나는 multiset을 사용하여 풀었다.

 

Naive한 방법으로 생각했을때, 배열을 탐색하여 중간값을 찾겠다고 한다면 시간복잡도 O(nm) 으로 시간초과가 될 것이라고 생각했다.

그래서 각  Query당 최대 O(log n) 만큼의 시간복잡도를 가지는 자료구조가 필요하다고 생각했고, 떠올린 것이 이진 트리였다.

그리고 숫자가 하나씩 들어오니까 다음 출력 값은 바로 전 출력된 값과 인접한 숫자들로 결정될 것이다라고 생각했다.

그래서 multiset을 사용하기로 했다.

multiset, 좌측에 있는 변수 개수 left, 우측에 있는 변수 개수 right를 이용하여 이전 중앙값과 이번 입력값의 대소에 따라 left, right가 변경되고, 이에 따라 이번에 출력할 중앙값을 다시 결정하면서 답을 출력한다.

코드는 다음과 같다. 코드를 보는게 글로 봐서 이해하는 것 보다 빠를 것이다.

#include <cstdio>
#include <set>

using namespace std;

int main(){
  
  int n,t;
  int left  = 0;
  int right = 0;
  
  int before_mid;
  multiset<int> s;
  
  scanf("%d",&n);
  scanf("%d",&t);
  printf("%d\n",t);
  
  s.insert(t);
  before_mid = t;
  auto it =  s.begin();
  
  for(int i=1;i<n;i++){
    scanf("%d",&t);
    s.insert(t);
    if(t < before_mid){
      left  += 1;
    }
    else{
      right += 1;
    }
    
    if(left - right >= 1){
      left -= 1;
      right += 1;
      --it;
    }
    else if(right -  left >= 2){
      left  +=  1;
      right -=  1;
      ++it;
    }
    
    printf("%d\n",*it);
    before_mid = (*it);
    
    //printf("left :  %d   right : %d  mid  : %d\n",left, right, before_mid);
  }
  
  
  
}

 

P.S. 이보다 빠르고 더 깔끔한 풀이가 있다. 삽입/삭제시 log n의 시간복잡도를 가지는 다른 자료구조를 사용한다면 더 빠르게 풀 수 있다. (set은 속도가 매우매우 느리다.)