[BOJ] 11279번 최대 힙 / 사용언어 : 파이썬(python)

※ 문제링크

11279번: 최대 힙

※ 관련개념 및 참고사이트 

[Python]우선순위 큐, heapq

해당문제는 우선순위 큐라는 자료구조의 개념을 알아야 풀 수 있는 문제였다. 우선순위 큐라는 개념부터 확실히 하기위해서 구글링을통해 우선순위 큐에 대한 조사를 하였고, 그 중에 개념설명이 잘 되어 있는 사이트가 있어 링크를 걸어놓았다. 파이썬에서는 해당 자료구조를 구현하기 위해 heapq패키지를 지원하고 있다. 자료구조의 개념에 대한 깊이 있는 이해와 숙달을 목표로 하는 사람이 아니라면그냥 만들어진 패키지를 적절히 활용하는 것이 더 좋으니 적극 활용하였다. 다만 heapq는 최소 힙만 지원을 하고 있어서 해당 문제를풀기 위해서는 약간의 변형이 필요하였다. 그래서 값을 넣을 때 튜플 형태로 변형하여 튜플의 첫번째 원소에는 우선순위를 두번째 원소에는 실제 변수의 값을 넣어 구현하였다. 자세한 풀이 방법과 코드는 아래와 같다.

1. 값을 입력받을 리스트를 생성한다.

2. 반복문을 통해 입력받은 값이 0이면 pop명령을 양의 정수이면 push명령을 수행해주고, pop명령 수행시에는 값을 출력해준다.

+ 해당 문제를 통과하기 위해서는 sys함수 사용이 필수적이다. 개행문자에 유의하여 작성해주자.

 

import heapq
import sys
N = int(input())
r_list = []
for i in range(N):
    K = int(input())
    if i == N-1:
        if K == 0:
            if len(r_list) == 0:
                # print(0)
                sys.stdout.write(f'0')
            else:
                # print(heapq.heappop(r_list)[1])
                sys.stdout.write(f'{heapq.heappop(r_list)[1]}')
        else:
            heapq.heappush(r_list, (-K, K))
    else:
        if K == 0:
            if len(r_list) == 0:
                # print(0)
                sys.stdout.write(f'0\n')
            else:
                # print(heapq.heappop(r_list)[1])
                sys.stdout.write(f'{heapq.heappop(r_list)[1]}\n')
        else:
            heapq.heappush(r_list, (-K, K))

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.