백준 1655 (가운데를 말해요) c++

문제

1655번: 가운데를 말해요

정수의 개수 n개가 한개씩 주어집니다. 주어지는 대로 중간값을 출력하면 되는 문제입니다.

정수의 개수가 짝수이면 중간값이 2개 이므로 둘중 작은 값을 출력하면 됩니다.

 

예를 들어 n이 5이고 처음에 1이들어오면 1을 출력하고

또 3이 들어오면 {1, 3} 중에 1이 작으므로 1을 출력하고

또 5가 들어오면 {1, 3, 5} 이므로 3을 출력하는 식으로 생각해주면 됩니다.

 

naive하게 생각해보면 n의 범위가 100000까지 이고 계속 숫자가 n개까지 주어질때 마다

정렬해주면 n * nlog n의 시간복잡도가 나와 시간 제한에 걸리게 됩니다.

 

예를 들어 다음과 같이 수가 주어졌을 때 숫자 k가 들어온다고 가정해보고 중간값이 될 수 있는 후보를

보겠습니다.

 

먼저 k가 현재 중간값인 8보다 클경우

8이 됩니다. (중간값 유지)

 

다음으로 k가 8 보다 작을 경우 입니다.

중간 값이 6으로 바뀌게 됩니다.

 

만약 k가 6 < k <8 이라면

k가 중간값이 됩니다.

 

따라서 이를 통해 알 수 있는 사실은 우리가 찾고자하는 중간값은 결국 기존 중간값 근처에서 결정납니다.

결국 절반으로 나누었을 때 경계에 있는 값입니다.

굳이 매번 모두를 정렬할 필요가 없습니다.

지금까지 들어온 수를 크기 기준으로 절반씩 나누어서 관리하는 것입니다.

왼쪽 배열이 작은 수가 들어가고 오른쪽 배열이 큰 수가 들어간다고 했을 때,

왼쪽 배열은 max heap, 오른쪽 배열은 min heap

왼쪽 배열.top() <= 오른쪽 배열.top()

 

저는 여기까지 아이디어는 떠올렸지만 주어진 수가 홀수인지 짝수인지에따라 구현이 달라진다는 점을

간과하였고 멘토님께 새로운 아이디어를 받아서 다시 풀어 해결하였습니다.

 

 

왼쪽의 배열의 크기와 오른쪽의 배열 크기가 다를 경우

즉, 현재 전체 주어진 수가 홀수인 경우

왼쪽 배열이 오른쪽 배열보다 항상 1개 더 많도록 유지

 

왼쪽의 배열의 크기와 오른쪽의 배열 크기가 같을 경우 

즉, 현재 전체 주어진 수가 짝수인 경우 

왼쪽 배열과 오른쪽 배열의 크기를 같게 유지

 

이 두가지 경우를 만족하는 순간 중간값은 결국 왼쪽 집합의 top()입니다.

 

2개의 Priority_queue로 관리하였습니다.

이렇게 하는 순간 시간복잡도 : O(NlogN) 이됩니다.

priority_queue<int>s;//max heap (왼쪽 집합)
priority_queue<int, vector<int>, greater<int>>b;//min heap (오른쪽 집합)

제가 처음에 작성한 코드 입니다.

n개의 숫자를 1개씩 입력받습니다. a로 입력

 

맨 처음에 두 배열은 비워져 있으므로 

1-5 번째 줄은 처음에 들어온 수를 처리하는 과정입니다.

그냥 처음에는 왼쪽 큐에 넣어줍니다.

 

6-17번째 줄은 2번째로 수가 들어왔을 경우입니다. 

왼쪽의 큐의 top()과 비교해 더 작으면 

swap 하는 부분입니다. 왼쪽의 큐 top()이 오른쪽의 큐 top()으로 가게 되고

2번째로 들어온 a가 왼쪽의 큐 top()으로 들어가게 됩니다.

그게 아니면 그냥 단순히 a를 왼쪽의 큐로 넣어줍니다.

 

지금 이러한 코드는 맨처음에 오른쪽, 왼쪽 큐가 아무것도 없으므로 따로 생각해서 작성한 코드입니다.

왼쪽의 큐와 오른쪽의 큐의 크기가 같을 경우입니다.

첫번째 if문은 현재 들어올 수가 중간값(s.top())보다 작거나 같을 경우

두번째 if문은 현재 들어올 수가 중간값(s.top()과 b.top())사이에 있을 경우 

세번재 if문은 현재 들어올 수가 중간값(s.top()) 보다 클 경우

왼쪽의 큐와 오른쪽의 큐가 다를 경우 입니다.

if문은 위의 코드와 같은 경우 입니다.

---

이렇게 작성할경우 너무 복잡해 보이고 코드를 이해하기 어려울것이라고 예측하였습니다.

따라서 다른 분들이 작성한 코드를 참조하였습니다.

위의 세가지 스크린샷의 코드를 이렇게 16줄의 코드로 완성하였습니다.

 

코딩을 할때 막무가내로 생각하면서 갈기지 말고 정리를 해가면서 코딩을 해야한다는 깨달음을 얻었습니다...

---

제가 처음에 작성한 전체 코드입니다. (정답은 맞았습니다)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n;
priority_queue<int>s;//내림
priority_queue<int, vector<int>, greater<int>>b;//오름
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i = 1, a; i <= n; i++) {
        cin >> a;
        if (i == 1) {
            s.push(a);
            cout << s.top() << '\n';
            continue;
        }
        if (i == 2) {
            if (a <= s.top()) {
                b.push(s.top());
                s.pop();
                s.push(a);
                cout << s.top() << '\n';
            }
            else {
                b.push(a);
                cout << s.top() << '\n';
            }
            continue;
        }
        if (s.size() == b.size()) {
            if (a <= s.top()) {
                cout << s.top() << '\n';
                s.push(a);
            }
            else if (s.top() < a && a < b.top()) {
                cout << a << '\n';
                s.push(a);
            }
            else {
                s.push(b.top());
                b.pop();
                b.push(a);
                cout << s.top() << '\n';
            }
        }
        else {
            if (a <= s.top()) {
                b.push(s.top());
                s.pop();
                s.push(a);
                cout << s.top() << '\n';
            }
            else if (s.top() < a && a < b.top()) {
                cout << s.top() << '\n';
                b.push(a);
            }
            else {
                b.push(a);
                cout << s.top() << '\n';
            }
        }
    }
 
    return 0;
}

---

다른 분들이 작성한 코드입니다. (훨씬 간결)

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
priority_queue<int>l;
priority_queue<int, vector<int>, greater<int>>r;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        if (l.size() == r.size()) {
            l.push(num);
        }
        else r.push(num);
        if (!l.empty() && !r.empty() && l.top() > r.top()) {
            int left = l.top();
            int right = r.top();
            l.pop();
            r.pop();
            l.push(right);
            r.push(left);
        }
        cout << l.top() << '\n';
    }
    return 0;
}