[C++] 1655번 가운데를 말해요 - 자료 구조, 우선순위 큐

1. 문제

• 백준이가 동생에게 숫자를 불러줄 때, 그때까지 불러준 수들 중 중간값을 동생이 말해야 한다.

<입력>

• - 1 -   백준이가 외치는 정수의 개수 \(N(1 \leq N \leq 100,000)\)
• - N줄 -   정수 \(num(-10,000 \leq num \leq 10,000)\)

<출력>

• 중간값

2. 재정의

• 수열들의 중간값 출력

3. 해결 방법

• 오름차순, 내림차순 우선순위 큐를 각각 하나씩 만든다.
• 오름차순 우선순위 큐의 top이 내림차순 우선순위 큐의 top보다 항상 작게 만들고 오름차순, 내림차순의 원소 수를 같게 한다면 항상 오름차순 우선순위 큐의 top이 중간값이다.

4. 실수한 점, 개선할 점

• 거의 다 생각했는데 끝을 생각해내지 못한 게 너무 아쉽다. 조금 체계적으로 사고하는 연습을 해야 할 필요가 있을 것 같다.

 

<코드>

#include <iostream>
#include <queue>

#define fastio ios_base::sync_with_stdio(0);

using namespace std;

const int MAX_N = 100001;

// <문제>
// 정수의 개수 N과 수열 A[i]
int N, A[MAX_N];

// 내림차순, 오름차순 priority_queue
priority_queue<int> upper_pq;
priority_queue<int, vector<int>, greater<int>> lower_pq;

void input() {
    cin >> N;
    for(int i=0; i<N; i++)
        cin >> A[i];
}

void solve() {
    for(int i=0; i<N; i++) {
        if(i&1)
            lower_pq.push(A[i]);
        else
            upper_pq.push(A[i]);
            
        if(!upper_pq.empty() && !lower_pq.empty() && upper_pq.top() > lower_pq.top()) {
            int a = upper_pq.top(), b = lower_pq.top();
            upper_pq.pop(); lower_pq.pop();
            upper_pq.push(b); lower_pq.push(a);
        }
        
        cout << upper_pq.top() << '\n';
    }
}

int main() {
    fastio;
    
    input();
    
    solve();
    
    return 0;
}

 

<문제 바로가기>

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

1655번: 가운데를 말해요

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.