728x90
반응형
※ 문제링크
1927번: 최소 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
※ 관련개념 및 참고사이트
[Python]우선순위 큐, heapq
큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진
velog.io
해당문제는 우선순위 큐라는 자료구조의 개념을 알아야 풀 수 있는 문제였다. 파이썬에서는 해당 자료 구조를 구현하기 위해 heapq 패키지를 지원하고 있다. 자료구조의 개념에 대한 깊이 있는 이해와 숙달을 목표로 하는 사람이 아니라면 만들어진 패키지를 적절히 활용하는 것이 더 좋으니 적극 활용하였다. 자세한 풀이 방법과 코드는 아래와 같다.
1. 값을 입력받을 리스트를 생성한다.
2. 입력받은 값이 0이면 pop명령을 양의 정수이면 push명령을 수행해주고, pop명령 수행시에는 값을 출력해준다.
+ 속도 개선을 위해서는 sys함수 사용하는 것이 좋다. 개행문자에 유의하여 작성해주자.
import sys
import heapq
r_list = []
T = int(input())
for i in range(T):
order = int(input())
if i == T-1:
if order == 0:
if len(r_list) == 0:
sys.stdout.write(f'0')
else:
sys.stdout.write(f'{heapq.heappop(r_list)}')
else:
heapq.heappush(r_list, order)
else:
if order == 0:
if len(r_list) == 0:
sys.stdout.write(f'0\n')
else:
sys.stdout.write(f'{heapq.heappop(r_list)}\n')
else:
heapq.heappush(r_list, order)
P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1655번 가운데를 말해요 / 사용언어 : 파이썬(python) (0) | 2021.12.28 |
---|---|
[BOJ] 11286번 절댓값 힙 / 사용언어 : 파이썬(python) (0) | 2021.12.27 |
[BOJ] 11279번 최대 힙 / 사용언어 : 파이썬(python) (0) | 2021.12.27 |
[BOJ] 12865번 평범한 배낭 / 사용언어 : 파이썬(python) (0) | 2021.12.26 |
[BOJ] 5430번 AC / 사용언어 : 파이썬(python) (0) | 2021.12.26 |
댓글