백준 / 1665 / 가운데를 말해요 / C++

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

1655번: 가운데를 말해요

 

시간초과로 인해 애를 많이 먹었던 문제입니다.

 

맨 처음에 문제를 보고 떠올린 풀이는 vector에 넣고 sort함수를 사용해서 가운데 수를 출력하는 것이었습니다.

문제의 시간제한이 0.1초이기 때문에 왠지 시간초과가 날 것 같다는 생각이 들었지만 ... 다른 풀이가 딱히 떠오르지

않아 풀이를 제출해보았는데 역시나 시간초과가 났습니다 :D 

 

그래서 밑에 힌트를 확인해보니 , 우선순위 큐가 나와있었습니다. 처음에 우선순위 큐를 생각 하긴 했었지만 막상 우선순위 큐를 쓴다해도 뾰족하게 문제를 해결할 방법이 떠오르지 않았기 때문에 단순한 구현이거나 다른 알고리즘이 있겠거니 생각하고 있었는데 우선순위 큐를 사용하는 문제라는 것을 확인하고 다시 곰곰히 생각해 봤습니다.

 

우선순위 큐에 입력값을 넣으면 분명 정렬은 되겠지만 index접근이 안되기 때문에 중간 값을 어떻게 가져와야 하는지 계속 고민해봤는데 떠오르지가 않았습니다 ㅜㅜ 한참 고민하다 구글링하여 대충 아이디어 힌트만 얻은 후에 스스로 구현해보자 생각하고 다른 분의 블로그를 참고하였습니다 ! (참고 블로그 : https://www.crocus.co.kr/625)

 

풀이를 보고나니 이걸 어떻게 생각 할 수 있을까 ... 라는 생각이 들기는 했지만 아직 많이 부족하기 때문에 저런 아이디어를 떠올릴 수 없었구나 반성하면서 이렇게 하나 또 배웠기 때문에 다음에 비슷한 문제가 나온다면 꼭 풀 수 있도록 여러 번 반복해서 봐야 할 좋은 아이디어라고 생각했습니다. 

 

풀이방법을 코드로 구현하는건 어렵지 않았는데 또 시간초과가 났습니다... 그리고 나서 참고한 블로그 주인분이 푸신 풀이를 봤는데 거의 똑같았고 입출력만 C형태로 scanf , printf로 달랐습니다. cin과 cout에 비해 scanf와 printf가 시간단축에 도움이 된다는 글을 많이봐서 바꿔서 출력했더니 정답처리 되었습니다. 위 부분에 대해서도 정확히 어떤이유로 차이가 나는건지 찾아서 공부해보고 포스팅 하도록 하겠습니다.   

 

시간초과가 발생하지 않는 최종풀이입니다.

#include <iostream>
#include <vector>
#include <queue>    
#include <algorithm>
 
using namespace std;
 
priority_queue<int, vector<int>, less<int>> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
 
 
 
int main()
{
    int N;
    scanf("%d", &N);
    
    for (int i = 0; i < N; i++)
    {
        int a;
        scanf("%d", &a);
        
        if (maxHeap.size() > minHeap.size())
        {
            minHeap.push(a);
        }
 
        else
        {
            maxHeap.push(a);
        }
 
        if (maxHeap.size() >= 1 && minHeap.size() >= 1)
        {
            if (maxHeap.top() > minHeap.top())
            {
                int a1 = maxHeap.top();
                int a2 = minHeap.top();
 
                maxHeap.pop();
                minHeap.pop();
                
                maxHeap.push(a2);
                minHeap.push(a1);
            }
        }
 
        printf("%d\n", maxHeap.top());
        
    }
 
 
 
 
 
    return 0;
}