[Baekjoon] 1927: 최소 힙 - (C3, S2) std::priority_cueue, 입출력 최적화

문제
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

1927번: 최소 힙

 

이 문제는 사실상 min heap을 구현하면 되는 쉬운 문제다. 직접 구현해도 그리 어렵지는 않으나, C++을 공부하고 있기에 C++의 컨테이너를 사용해 풀어보았다.

 

C++은 priority_queue 컨테이너를 지원한다. 이는 기본적으로 max heap으로 동작하지만, 다음과 같이 min heap으로 설정할 수 있다.

priority_queue<int, vector<int>, greater<>> min_heap;

 

priority_queue 컨테이너는 push, pop, top, empty 등의 함수를 지원하기 때문에 다음과 같이 쉽게 구현이 가능하다. 

 

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

int main()
{
    priority_queue<int, vector<int>, greater<>> min_heap;
    int N, x;

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> x;
        if (x) // if x isn't 0
            min_heap.push(x);
        else
        {
            if (min_heap.empty())
                cout << 0 << '\n';
            else
            {
                cout << min_heap.top() << '\n';
                min_heap.pop();
            }
        }
    }

    return 0;
}

그런데, 이 코드를 제출해보면 반례는 없지만 시간 초과로 실패한다. 그 이유는 이 문제는 시간 제한이 1초로, 성능 최적화가 중요한 문제이기 때문이다. 이는 많은 입출력이 병목 현상을 초래한 것으로 보인다. 이를 해결하기 위해 다음과 같은 방법을 사용하였다. 

 

ios::sync_with_stdio(false);

이 설정은 C++ 표준 입출력(cin, cout)과 C 표준 입출력(scanf, printf)의 동기화를 끊어 입출력 속도를 향상시킨다. 기본적으로 C++은 C의 표준 입출력도 지원하므로 이러한 동기화를 해제하여 속도를 높이는 효과가 있다. 단, 이 설정 이후에는 C++과 C의 입출력을 혼용할 수 없다.

 

cin.tie(nullptr);

이 설정은 cin과 cout의 자동 연결을 끊어, cin 호출 시 발생하는 cout 버퍼의 자동 플러시(flush)를 비활성화한다. C++은 기본적으로 cin 호출 시 cout의 버퍼가 자동으로 플러시된다. 이를 끊으면 불필요한 플러시가 발생하지 않아 성능이 향상되지만, 입출력 순서를 명확히 관리해야 하며 cout으로 출력된 데이터가 버퍼에 남아 출력이 정상적으로 이루어지지 않는 문제 등이 발생할 수 있다. 

 

채점 결과를 먼저 확인해보자.

첫 번째 제출(아래)는 위의 코드를 그대로 제출했을 때이다. 50%에서 멈췄고, 시간 초과가 발생했다.

 

그리고 두 번째는 위 두 설정을 모두 사용했을 때이다. 확실히 실행 시간이 12ms로, 성능이 크게 향상된 것을 볼 수 있다. 세 번째 제출은 ios::sync_with_stdio(false); 설정만을 사용했을 때이다. 그리고 마지막 네 번째 제출은 cin.tie(nullptr); 설정만을 사용했을 때이다. 두 가지를 모두 사용했을 때보다는 느리지만, 60ms로 성능이 향상된 것을 볼 수 있다. 

 

결국, cin.tie(nullptr); 설정이 성능 향상에 크게 기여하여 실행 시간을 줄이는 효과가 있었다. 

 

최종 코드

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    priority_queue<int, vector<int>, greater<>> min_heap;
    int N, x;

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> x;
        if (x) // if x isn't 0
            min_heap.push(x);
        else
        {
            if (min_heap.empty())
                cout << 0 << '\n';
            else
            {
                cout << min_heap.top() << '\n';
                min_heap.pop();
            }
        }
    }

    return 0;
}

 

한가지 짚고 넘어갈 것은, 이 설정 사용 시 버퍼가 자동으로 플러시되지 않아 출력 지연 문제가 발생할 수 있다. 그러나 문제에서 개행을 위해 사용한 escape sequence '\n'이 일종의 플러시 역할을 함께 수행함으로써, 이런 문제가 발생하지 않았으리라 추측해본다.

다만 이는 콘솔 환경과 구현 등에 따라 다르게 나타날 수 있는 비표준적인 동작이다. C++ 표준에서는 '\n'이 버퍼를 플러시하지 않으며, 대신 std::endl이 개행과 플러시를 동시에 수행하는 것이 보장된다. 따라서, 위 현상은 단순히 '\n'이 플러시를 수행했기 때문이라고 단정하기 어렵다.

따라서서 이는 추측일 뿐, 단순히 100,000개의 입출력 연산이 최적화된 설정과 함께 문제를 일으키지 않았기 때문에 정상적으로 동작했다고 보는 것이 타당하리라고 본다.