[백준] 11279 최대힙 (시간초과 해결)

SuJin·2021년 3월 29일
0

Algorithm

목록 보기
1/3


이렇게 예제 문제를 손으로 하나씩 직접 풀어보면서 코드를 짜봤다.
코드를 다 짰을때 분명 예제가 다 맞고 나는 코드를 올바르게 짰는데
채점중(3%) 뜨고 "시간초과" 가 떠버려서 인터넷을 찾아보다가 cin과 cout을 사용하면 시간초과가 나는 경우가 생긴다는것을 발견했다!!! 그래서 scanf와 printf를 사용했더니 성공했다!!!!!
백준 질문에서 보니까 cin.tie(NULL)을 사용하라는 글을 봤는데 이거 cin cout 사용할때는 이 방법이 먹히지 않았다ㅠㅠ

#include <iostream>
#include <queue>
#include <stdio.h>
using namespace std;

int main()
{
    cin.tie(NULL);
    int n;
    scanf("%d", &n);

    priority_queue<int> x;
    int a;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a);

        if (a == 0)
        {
            if (x.empty() == 1)
                printf("%d\n", 0);
            else
            {
                printf("%d\n", x.top());
                x.pop();
            }
        }
        else
            x.push(a);
    }
    return 0;
}

최대힙 문제를 풀때 "우선순위큐"를 사용하면 쉽게 문제를 풀 수 있다.
우선순위큐는 큐와 똑같이 FIFO구조이면서, 데이터가 들어오는대로 크기에 맞춰 내용물을 재정렬하는 것이다.
예를들어,
5, 2, 4, 6, 1 순서대로 큐에 push하면 우선순위큐에는
①②④⑤⑥ 이렇게 정렬이 되어서 pq.top() = 6 이고, pq.pop()해주면 6이 pop되는 것이다!

이렇게 딱 맞았습니다가 떠버렸다ㅠㅠㅜ 감격..!!!

ps. 근데 이거 이미지 크기 조절이 안되는건가..?? 필기 올려둔거 너무 크다ㅠㅠ 글씨 색도 정하고 싶은데 잘 안되네....ㅠ

profile
Anyone can be anything.

0개의 댓글