큐 (심화편)

백준 11279

 

import sys

N = int(sys.stdin.readline())

answerqueue = []

for i in range(N) :

    comein = int(sys.stdin.readline())

    if comein == 0 :

        if len(answerqueue) == 0 :

            print(0)

        else:

            answerqueue.sort()

            print(answerqueue.pop())

    else :

        answerqueue.append(comein)

 

Queue를, list를 활용해서 구현하였다.

다만 이때 시간 복잡도가 N*O(NLOGN)으로써 , 1000000000000정도가 된다. (N제약이 100000) 

 

즉, 정렬을 따로 하지 않고도, 최대나 최소를 얻어낼 수 있는 자료구조를 사용하는 것이 좋겠다는 판단이 들었다. 

 

heapqueue -> push 될 때 heap의 구조를 따라 크기에 맞춰 들어가는 자료구조

 

heap(sort를 기억할 것이다) + queue의 개념으로 생각하는 것이 쉽다. 

해당 heapqueue는, push 될때 자동으로 크기에 맞춰 들어가게 된다

 

1. import heapq

2. heapq.heappush(arr,원하는 값)

3. heapq.heappop(arr)

 

<heapq는 기본적으로, 최솟값을 반환한다. 그러므로 trick을 위해선

2. heapq.heappush(arr,-원하는값)

3. -heapq.heappop(arr)

 

로 최댓값을 반환할 수 있다. ( 정렬없이!)

 

import sys

import heapq

N = int(sys.stdin.readline())

answerqueue = []

for i in range(N) :

    comein = int(sys.stdin.readline())

    if comein >0 :

        heapq.heappush(answerqueue,-comein)

    else:

        if len(answerqueue) == 0 :

            print(0)

            continue

        else:

            print(-heapq.heappop(answerqueue))

       

 

백준 11826

import sys

import heapq

N= int(sys.stdin.readline())

answer = []

for i in range(N) :

    nextcome = int(sys.stdin.readline())

    if nextcome!= 0:

        heapq.heappush(answer,[abs(nextcome),nextcome])

    else:

        if len(answer) > 0 :

            print(heapq.heappop(answer)[1])

        else:

            print(0)

 

 

문제 format도 어렵지 않았지만, 정리를 위해 작성한다. 

 

heappush로 2개의 원소를 가진 배열을 push하면, 

[0,1] 중 0의 조건중 최소를 먼저, 그 다음에 1의 조건중 최소에 대해 pop시 정렬된다.