1655번:가운데를 말해요

다시 알고리즘 공부를 하기 시작했다.

한참 안해서 그런지 예전에 잘풀던 쉬운 문제도 쉽게 풀리지 않는다.

다시 처음부터 차근차근히 꾸준히 풀어야겠다. 

처음부터 잘하는 사람은 없으니까!

---

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

1655번: 가운데를 말해요

브론즈 문제들을 휙휙 풀다가,

골드 문제가 하나 껴있어서 쉽겠지 하고 도전했는데 ㅋㅋㅋㅋ

결국 혼자 힘으로만 풀지 못했다. 

 

1655번: 가운데를 말해요

---

1번째 시도 : 

위의 설명과 같이 외친 순서대로, 새로 수가 외쳐질때마다 그 수 중에서 중간값을 출력하는 문제다.

조금 유의해야할 부분이라면 짝수개일때와 홀수개일때를 가리는 것이라 생각했고,

vector를 사용하고 sort해서 해결하면 될 것이라 생각했다.

 

그리고 신나게 구현을 하고 제출했는데 ㅋㅋ

//가운데를 말해요
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> cal;
vector<int> ans;

int main(void)
{
    int N;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int n;
        cin >> n;

        cal.push_back(n);
        sort(cal.begin(), cal.end());

        if (cal.size() % 2 == 0)
        { //백준이가 외친 수의 개수가 짝수개라면
            ans.push_back(cal[cal.size() / 2 - 1]);
        }
        else
        { //홀수개라면
            ans.push_back(cal[cal.size() / 2]);
        }
    }

    for (int i : ans)
        cout << i << endl;

    return 0;
}

맞왜틀..? 시간초과임을 보고 나서 문제를 다시 봤는데 시간제한이 0.1초...?

출력할때마다 sort는 절대 맞는 방법이 아닌거 같고 우선순위 큐를 사용해야함을 깨달았다...

왜 항상 문제를 똑바로 읽지 않고 마음이 앞서는지 ㅋㅋㅋㅋㅋ

 

근데 생각해보니 그럼.. 큐에 삽입할때는 뭐 자동정렬 된다고 치자.. 중간값을 출력하기 위해서는 ...? 

 

구글 검색을 했다. ㅎㅎ

 

우선순위 큐와 Heap 자료구조를 이용하는 문제였다. 

---

풀이 방식

0. max_pq과 min_pq 두 개의 우선순위 큐가 필요하다

1. max_pq과 min_pq의 원소 개수는 항상, (1)같거나 (2)최대힙이 1개 더 많아야한다.

   max_pq.size()==min_pq.size()  or  max_pq.size()==(min_pq.size()+1)

 

2. max_pq의 원소는 모두 min_pq의 원소보다 작거나 같다.

3. max_pq.top()이 min_pq.top()보다 큰 경우 swap 한다. (2의 규칙을 위반하기 때문)

 

---

두번째 시도 :

아 이걸 혼자서 어떻게 생각해.. 궁시렁 거리면서 와다다닥 코드를 짰다.

//가운데를 말해요_골드 2
#include <iostream>
#include <queue>
#include <vector>
#include <functional> //greater, less

using namespace std;

priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int n;
        cin >> n;

        if (max_pq.size() == min_pq.size())
        { //둘이 size가 같으면 최대힙에 추가
            max_pq.push(n);
        }
        else
        {
            min_pq.push(n);
        }

        if (!max_pq.empty() && !min_pq.empty() && (max_pq.top() > min_pq.top()))
        {
            //최대합의 top이 최소합의 top보다 크면 교체
            int tmp = max_pq.top();
            max_pq.pop();
            max_pq.push(min_pq.top());
            min_pq.pop();
            min_pq.push(tmp);
        }

        cout << max_pq.top() << endl;
    }
}

아 이제 완벽하다 !!! 하고 제출했는데 

????????????????? 아니 또 시간초과? 아니 이보다 완벽할 수 없는데 왜 틀렸지... 하다가 한참 백준 알고리즘 풀때가 생각이 나면서 endl이 생각이 났다.. 망할 ㅡㅡ 

* endl은 출력버퍼를 비워서 \n보다 시간이 더 오래걸린다.

 

세번째 시도 :

//가운데를 말해요_골드 2
#include <iostream>
#include <queue>
#include <vector>
#include <functional> //greater, less

using namespace std;

priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int n;
        cin >> n;

        if (max_pq.size() == min_pq.size())
        { //둘이 size가 같으면 최대힙에 추가
            max_pq.push(n);
        }
        else
        {
            min_pq.push(n);
        }

        if (!max_pq.empty() && !min_pq.empty() && (max_pq.top() > min_pq.top()))
        {
            //최대합의 top이 최소합의 top보다 크면 교체
            int tmp = max_pq.top();
            max_pq.pop();
            max_pq.push(min_pq.top());
            min_pq.pop();
            min_pq.push(tmp);
        }

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

백준... 꾸준히 풀어야겠다. 한참 안했더니 요지경 :(