글 읽기 - 시간초과가 나는데 이유를 알고싶습니다..

carpediemsh 7년 전 0

시간초과가 납니다.. max_heap 과 min_heap으로 풀어보았습니다.

push & pop시에 logN의 시간이 걸리는걸로 알고 있는데 왜 시간초과가 날까요?

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

priority_queue<int, vector<int>, less<int>> max_heap; //left
priority_queue<int, vector<int>, greater<int>> min_heap; //right


int main(){
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        int input;
        cin >> input;
        
        if(max_heap.size() == min_heap.size()){ //push left
            if(max_heap.size() == 0 && min_heap.size() == 0){
                max_heap.push(input); //init
            }
            else{
                if(min_heap.top() < input){
                    int temp = min_heap.top();
                    min_heap.pop();
                    min_heap.push(input);
                    max_heap.push(temp);
                    
                }
                else{
                    max_heap.push(input);
                }
            }
        }
        else if(max_heap.size() > min_heap.size()){//push right
            if(max_heap.top() > input){
                int temp = max_heap.top();
                max_heap.pop();
                max_heap.push(input);
                min_heap.push(temp);
            }
            else{
                min_heap.push(input);
            }
        }
        cout << max_heap.top() << "\n";
    }
    
    return 0;
}

waylight3 7년 전 2

아무리 봐도 맞는 것 같아서 혹시나 cin cout 문제인듯 싶어 제출해보니 실제로 맞았습니다를 받았습니다.

main문 처음에 다음 두 코드를 넣어주시면 cin, cout의 동기화 설정을 꺼서 입출력 속도를 높일 수 있습니다.

ios::sync_with_stdio(false);
cin.tie(0);

carpediemsh 7년 전 1

waylight3님 감사합니다.

가끔 cin, cout 때문에 시간초과가 났었는데

이번에는 그 생각을 하지 못하였네요 ...

scanf와 printf를 사용하여 제출하니 맞았습니다. 감사드립니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 나는데 이유를 알고싶습니다..

carpediemsh 7년 전 0

waylight3 7년 전 2

carpediemsh 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말