알고리즘 문제
백준 - 가운데를 말해요 (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)의 첫 번째 값이 중간값이 될 것이다. 이를 구현하기 위한 절차는 다음과 같다.
- 우선순위 큐를 두 개 생성한다. (편의상 leftSide, rightSide로 명명. push할 때는 leftSide는 내림차순이 되게, rightSide는 오름차순이 되게)
- 숫자를 하나씩 입력받는다.
- 만약 leftSide와 rightSide의 size가 같을 경우, leftSide에 주어진 숫자를 push한다.
- 만약 leftSide의 size가 더 클 경우 rightSide에 push한다.
- 만약 둘 다 비어있지 않으면서, leftSide의 첫 번째 숫자가 rightSide의 첫 번째 숫자보다 값이 클 경우, 값을 교체한다.
- 만약 leftSide와 rightSide의 size가 같을 경우, leftSide에 주어진 숫자를 push한다.
- leftSide의 첫 번째 숫자를 출력한다.
예를 들어 1, 2, 3, 4, 5 순서로 입력될 경우, 다음과 같다.
- 입력: 1
- left: 1
right: X - 결과: 1
- left: 1
- 입력: 2
- left: 1
right: 2 - 결과: 1
- left: 1
- 입력: 3
- left: 3, 1
right: 2 - 3과 2 교체
left: 2, 1
right: 3 - 결과: 2
- left: 3, 1
- 입력: 4
- left: 2, 1
right: 3, 4 - 결과: 2
- left: 2, 1
- 입력: 5
- left: 5, 2, 1
right: 3, 4 - 5, 3 교체
left: 3, 2, 1
right: 5, 4 - 결과: 3
- left: 5, 2, 1
이를 코드로 구현하면 다음과 같다.
#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;
}