알고리즘 문제

백준 - 가운데를 말해요 (1655번, C++)

als982001 2025. 1. 4. 17:44

Image by Gerd Altmann from Pixabay

 


 

링크

 

 이 문제는 이전에 풀어본 문제인데 풀어본지 너무 오래되어 다시 풀어보았다. 아무튼 이 문제는 일련의 숫자들이 주어질 때, 각 순간의 중간값을 알아내는 문제이다. 이를 위해서는 숫자들을 정렬할 필요가 있어 보인다. 하지만 시간 제한도 그렇고, 숫자가 주어질 떄마다 정렬을 하는 것은 별로 좋은 방법이 아닌 것 같다. 그래서 이전에 제출한 코드를 통해, 일이 정렬하지 말고 중간값을 알아내기 위한 두 개의 힙 혹은 우선수위 큐를 이용하면 좋다는 힌트를 얻게 되었다.

 

 예를 들어 특정 시점에서 주어진 숫자들이 1, 5, 4, 7, 2, 6, 3, 인 경우, 이를 1, 2, 3, 4, 5, 6, 7,로 정렬한 후 중간값 5를 찾는 것이 가장 쉬울 수 있으나 문제 조건 상 쉽지 않기에 중간값 5를 명확히 알 수 있게 (예를 들어) 두 개의 우선순위 큐 5, 3, 2, 1과 7, 4, 6로 분리하는 것이다. 이 때 첫 번째 우선순위 큐(5, 3, 2, 1, 9)의 첫 번째  값이 중간값이 될 것이다. 이를 구현하기 위한 절차는 다음과 같다.

 

  1. 우선순위 큐를 두 개 생성한다. (편의상 leftSide, rightSide로 명명. push할 때는 leftSide는 내림차순이 되게, rightSide는 오름차순이 되게)
  2. 숫자를 하나씩 입력받는다.
    • 만약 leftSide와 rightSide의 size가 같을 경우, leftSide에 주어진 숫자를 push한다.
      • 만약 leftSide의 size가 더 클 경우 rightSide에 push한다.
    • 만약 둘 다 비어있지 않으면서, leftSide의 첫 번째 숫자가 rightSide의 첫 번째 숫자보다 값이 클 경우, 값을 교체한다.
  3. leftSide의 첫 번째 숫자를 출력한다.

 

예를 들어 1, 2, 3, 4, 5 순서로 입력될 경우, 다음과 같다.

 

  1. 입력: 1
    • left: 1
      right: X
    • 결과: 1
  2. 입력: 2
    • left: 1
      right: 2
    • 결과: 1
  3. 입력: 3
    • left: 3, 1
      right: 2
    • 3과 2 교체
      left: 2, 1
      right: 3
    • 결과: 2
  4. 입력: 4
    • left: 2, 1
      right: 3, 4
    • 결과: 2
  5. 입력: 5
    • left: 5, 2, 1
      right: 3, 4
    • 5, 3 교체
      left: 3, 2, 1
      right: 5, 4
    • 결과: 3

 

이를 코드로 구현하면 다음과 같다.

 

#include <iostream>
#include <queue>

#define MAX 100001

using namespace std;

int N, num;
priority_queue<int> leftSide, rightSide;

int main()
{
    scanf("%d", &N);
    
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &num);
        
        if (leftSide.size() == rightSide.size())
            leftSide.push(num);
        else
            rightSide.push(-num);
            
        if (leftSide.empty() == false && rightSide.empty() == false)
        {
            int leftSideBiggestNum = leftSide.top();
            int rightSideBiggestNum = -rightSide.top();
            
            if (leftSideBiggestNum > rightSideBiggestNum)
            {
                leftSide.pop();
                rightSide.pop();
                
                leftSide.push(rightSideBiggestNum);
                rightSide.push(-leftSideBiggestNum);
            }
        }
        
        printf("%d\n", leftSide.top());
    }

    return 0;
}