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

문제 링크

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

---

◆문제 해결 및 설명◆

문제 해설 : 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

 

시간 제한이 0.1초임으로 정렬이되는 자료형에서 중간을 빠르게 뽑아낼 수 있어야 한다. 

그런 자료형이 있던가... 생각하다가 다른분의 코드를 보고 영감을 얻어 우선순위 큐 2개를 사용하여 중간 값을 바로 확인 가능하게 구현하였다.

왼쪽에는 최대 큐, 오른쪽에는 최소 큐를 배치하여 구현하였다. 이때 규칙이 있다.

 

1. 각각의 큐의 길이 차이가 1이상 나지 않아야한다.

- 따라서 큐에 대한 값의 push는 번갈아가면서 일어난다.

2. 항상 최대 큐의 top 값이 최소 큐의 top보다 작아야 한다.

- 매 push연산 후 비교를 통해 옳도록 swap해준다.

 

예제 입력1 에 대한 진행 과정을 보여드리겠다.

왼쪽 최대 큐부터 입력을 받게 하여서 왼쪽 top이 항상 답이 되도록 구현하였다.

이를 위해 입력은 왼쪽과 오른쪽 순서대로 값을 push해주고, 왼쪽 큐의 top이 더 큰 상황에만 Swap연산을 해준다.

빨간줄은 Input Value와 변경 점을, 형광펜은 출력 값을 나타낸다. 

출력이 항상 왼쪽 큐의 top값인 이유는 홀수 일때는 왼쪽 큐는 오른쪽 큐보다 항상 길이가 길어  왼쪽의 top이 중앙이고, 짝수일 경우에는 2번조건 때문에 값이 낮은 왼쪽을 출력해야하기 때문이다.

 

그런데 입력 예제로는 Swap에 대한 것을 보여드릴 수 없어 임의로 Input 3을 하였습니다

이렇게 Swap을 통해 왼쪽 큐가 항상 작음을 보장하여 왼쪽 큐의 top을 출력하는 것으로 답을 제출할 수 있습니다.

 

◆코드 전문◆

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int inputCount;
    cin >> inputCount;
    priority_queue<int, vector<int>, greater<int>> rightMinQue;
    priority_queue<int, vector<int>, less<int>> leftMaxQue;

    int inputValue;
    cin >> inputValue;
    leftMaxQue.push(inputValue);
    cout << leftMaxQue.top() << "\n";

    for (int i = 1; i < inputCount; i++)
    {
        cin >> inputValue;

        if (i % 2 == 1)
        {
            rightMinQue.push(inputValue);
        }
        else
        {
            leftMaxQue.push(inputValue);
        }

        if (leftMaxQue.top() > rightMinQue.top())
        {
            int left_top = leftMaxQue.top();
            int right_top = rightMinQue.top();
            leftMaxQue.pop();
            rightMinQue.pop();
            leftMaxQue.push(right_top);
            rightMinQue.push(left_top);
        }

        cout << leftMaxQue.top() << "\n";
    }

    return 0;
}