[baekjoon] 1655번 : 가운데를 말해요 (C++)

최대힙과 최소힙을 이용하면 쉽게 풀 수 있는 문제였당..

 

값이 들어올 때마다 중간값을 출력하게 되면 시간 복잡도가 증가하고 이 문제는 시간 제한이 있기 때문에... 다른 방법이 필요했다

 

여기서 조건은 

1. 최소 힙의 값들은 모두 최대 힙보다 큼

2. 최대 힙의 크기가 최소 힙의 크기보다 1 크거나 같도록 유지하면서 값을 넣어야 함

3. 값을 넣어준 후에 최대 힙과 최소 힙의 top 값을 비교해 최소 힙의 top보다 최대 힙의 top이 더 크다면 swap함

 

arr[] = { 1, 5, 2, 10, -99, 7, 5 } ← 배열이 이렇다면

 

[1 삽입]

- maxH = 1

- minH

→ 출력 : 1

 

[5 삽입]

- maxH = 1

- minH = 5

→ 출력 : 1

 

[2 삽입]

- maxH = 1 2

- minH = 5

→ 출력 : 2

 

[10 삽입]

- maxH = 1 2

- minH = 5 10

→ 출력 : 2

 

[-99 삽입]

- maxH -99 1 2

- minH = 5 10

→ 출력 : 2

 

[7 삽입]

- maxH = -99 1 2

- minH = 5 7 10

→ 출력 : 2

 

[5 삽입]

- maxH = -99 1 2 5

- minH = 5 7 10

→ 출력 : 5

 

만약 맨 마지막에 5가 아니라 6이 삽입되었다면?

- maxH = -99 1 2 6

- minH = 5 7 10

이렇게 되지만 maxH의 top이 minH의 top보다 크게 되므로 swap해서

- minH = -99 1 2 5

- minH = 6 7 10

→ 출력 : 5

 

여기서 최대힙과 최소힙을 구현하기 위해 priority_queue container을 이용할 수 있음

- 우선순위 큐 구현(vector, deque container와 붙여서 사용 가능)

- <queue 헤더 파일>

 

형식

priority_queue<Data Type> 변수 이름

- 기본 생성자 형식

bool empty() const; 

- 비어있으면 0 반환

size_type size() const;

- 원소 개수

const value_type & top() const;

- 맨 위 원소 반환(top 반환)

void push(const value_type & val);

- push 기능

void pop(); 

- pop 기능

 

[전체코드]

// BOJ 1655 가운데를 말해요
#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); // 입출력 빠르게 처리
    cin.tie(NULL);
    cout.tie(NULL);

    priority_queue<int> maxH; // 최대 힙
    priority_queue<int, vector<int>, greater<int> > minH; // 최소 힙
    int n, elem; // n : 숫자 개수 / elem : 입력하는 수
    cin >> n; // n 먼저 입력받음

    for(int i = 0; i < n; i++){
        cin >> elem; // 숫자를 하나씩 입력받음
        if(maxH.size() == minH.size()) // 최대힙과 최소힙의 크기 같을 때
            maxH.push(elem); // 최대 힙에 push
        else // 최대 힙이 더 클 때
            minH.push(elem); // 최소 힙에 push

        if(!minH.empty() && !maxH.empty()){ // 둘 다 비어있지 않고
            if(maxH.top() > minH.top()){ // 최대 힙의 top이 더 클 때
                int temp_max = maxH.top(); // 각자의 값을 swap 
                int temp_min = minH.top(); 
                maxH.pop();
                minH.pop();
                maxH.push(temp_min);
                minH.push(temp_max);
            }
        }
        cout << maxH.top() << "\n"; // 최대 힙의 top을 매번 출력 (중간값)
    }
}

 

나는 이 문제를 풀면서 시간초과가 계속 나서 이유를 고민했는데

결정적인 이유는

cout << maxH.top() << endl;

바로 이것 때문이었다

줄바꿈 때문에 endl을 썼었는데 그것보다 "\n"을 쓰는게 더 실행 속도가 빠르다.... 몰랐음

 

그리고

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이 코드를 쓰면 입출력을 더욱 빨리 처리할 수 있다고 하니 알아두어야겠다!! 

 

실행결과