Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 파이썬
- date_format
- 약수구하기
- 이진탐색
- set
- heapq
- 스택
- 딕셔너리
- dfs
- IH
- 오픽독학
- 오픽
- 제곱근
- 백준
- not null
- 완전이진트리
- 구현
- 슬라이싱
- %H
- Inner Join
- 삼중for문 탈출
- bfs
- Deque
- 우선순위큐
- issubset
- 최대재귀높이
- 복사
- 재귀
- 파일명 변경
- 브루트포스
Archives
- Today
- Total
나예
[프로그래머스] 이중우선순위큐(파이썬,heapq) 본문
1. 문제
https://school.programmers.co.kr/learn/courses/30/lessons/42628#
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
2. 풀이
우선순위 큐 heapq 이용함
(1) I인 경우 heappush
(2) D -1 인 경우 -> 빈 배열인지 확인 후 아니면 pop하면 최소값 빠짐
(3) D 1 인 경우 -> 빈 배열인지 확인 후 아니면 max값 구해서 remove
<처음 안 사실>
- [16,16,16] 에서 remove(16)을 하면 []가 아니라 [16,16] 임
- 우선순위큐로 q를 이용하고 있지만 애초에 리스트 타입이라 max 값 구해서 뺴줘도 됨( 최대힙 따로 안구해도 된단 뜻)
3. 코드
import heapq
def solution(operations):
answer = [0,0]
q= []
for oper in operations:
inst, num = oper.split()
if inst == "I":
heapq.heappush(q,int(num))
elif inst == "D" and num[0] == "-":
if len(q) !=0:
heapq.heappop(q)
else:
if len(q) != 0 :
find_max = max(q)
q.remove(find_max)
print(q)
if len(q) !=0:
answer[0] = max(q)
answer[1] = min(q)
return answer
* heapq에 익숙해지기 위해 최대힙으로 위의 문제를 풀어본 코드
import heapq
def solution(operations):
answer = [0,0]
q= []
for oper in operations:
inst, num = oper.split()
if inst == "I":
heapq.heappush(q,-int(num))
elif inst == "D" and num[0] == "-":
if len(q) != 0:
max_q = max(q)
q.remove(max_q)
else:
if len(q) != 0:
heapq.heappop(q)
print(q)
if len(q) !=0:
answer[1] = -max(q)
answer[0] = -min(q)
return answer
728x90