-
11279. [Python]최대 힙Python_알고리즘/Silver I 2024. 1. 9. 01:58
1. 문제
https://www.acmicpc.net/problem/11279
11279번: 최대 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 256MB
- 우선순위 큐
3. 파이썬 코드
import heapq import sys input = sys.stdin.readline num_list = [] N = int(input()) for _ in range(N): # 인풋 값 체크 input_num = int(input()) # 인풋 값이 0 인 경우 if input_num == 0: # num_list 값이 존재하는지 체크 if num_list: # 값이 있는 경우 heappop을 사용하여 최소값 출력하며 - 붙이면 최대값이 됨 print(-heapq.heappop(num_list)) else: # 외의 경우 0 출력 print(0) else: # 값을 넣을때 최대값을 뽑기위해 -를 붙여서 값을 너어줌 heapq.heappush(num_list, -input_num)
4. 문제를 풀고난 후 생각
- 우선순위 큐를 이용하여 문제를 해결했다.
- 우선순위 큐의 경우 최소값을 0번 인덱스로 보내주기 때문에 값을 넣어줄때 음수로 값을 넣어주면 최대 값이 음수로 0번 인덱스에 저장되게 된다.
- 이후 값을 출력하는 부분에서 최소값을 뽑아주며 다시 - 부호를 붙일 경우 최대값이 되므로 문제에서 요구하는 답을 나타낼 수 있다.
5. 문제를 푸는데 도움이 되는 지식
- 우선순위 큐
'Python_알고리즘 > Silver I' 카테고리의 다른 글
1932. [Python]정수 삼각형 (0) 2024.04.22 1141. [Python] 접두사 (0) 2024.04.09 1946. [Python]신입 사원 (0) 2023.12.19 1926. [Python]그림 (0) 2023.12.09 1342. [Python]행운의 문자열 (1) 2023.12.08