https://school.programmers.co.kr/learn/courses/30/lessons/42628
문제 파악
operations 라는 배열이 주어진다.
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
규칙이 세가지 있다.
1. 'I 숫자' : 해당 숫자를 큐에 삽입한다.
2. 'D 1' : 큐에서 최댓값을 삭제한다.
3. 'D -1' 큐에서 최솟값을 삭제한다.
operations배열에 모든 연산을 수행한 후, 큐가 비어있으면 [0,0],
비어있지 않으면 [최댓값,최솟값]을 return 하도록 하는 함수를 구현해야한다.
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"] 에 대해 연산을 수행해보면,
q = []
1. I -45 : q = [-45]
2. I 653 : q = [-45,653]
3. D 1 : q = [-45]
4. I -642 : q = [-45,-642]
5. I 45 : q = [-45,-642,45]
6. I 97 : q = [-45,-642,45,97]
7. D 1 : q = [-45,-642,45]
8. D -1 : q = [-45,45]
9. 333 : q = [-45,45,333]
모든 operations를 다 썼고, 큐가 비어있지 않으니 [최댓값,최솟값] 형식으로 return
answer = [333,-45]
해결 아이디어
최댓값, 최솟값을 구해야하고 push,pop 을 사용해야하니 heapq 자료구조를 활용하자.
operations 배열 내 명령어(op)들을 하나씩 순회할건데:
op문자열의 0번째 인덱스가 I면:
# tail = s.split(" ", 1)[1]
op문자열을 공백을 기준으로 split하여 그 뒷 덩어리를(숫자) q에 append해준다.
op문자열의 0번째 인덱스가 D이면 그리고 q가 비어있지 않으면:
op문자열의 마지막, 즉 [-1]번째 인덱스가 1이면:
q에 최솟값을 pop해준다.
op문자열의 마지막, 즉 [-1]번째 인덱스가 -1이면:
q에 최댓값을 pop해준다.
# operations 순회가 끝났으면 완성된 q에서 [최댓값, 최솟값] 형식으로
answer = [] 배열에 넣어준다.
이렇게 풀던 와중 문제가 생겼다.
어떨땐 최소를 어떨땐 최대를 pop해야하니까
min_q, max_q 두개의 리스트를 만들어서 관리하려 했는데
pop을 할 시 두 개의 큐를 동기화해주는 작업이 필요했다.
valid라는 리스트를 만들어주고, max_q에서 pop을 했으면, 나중에 min_q에 pop할때 이 valid 리스트를 확인해서 True이면, 즉 이미 방문했으면 한번 넘어가는 로직으로 처리해준다.
해답 및 풀이
import heapq
def solution(operations):
min_q = []
max_q = []
valid = [False] * len(operations) # 각 연산별 원소 유효 여부
for i, op in enumerate(operations):
cmd, n = op.split() # op를 명령어와, 숫자로 분리
n = int(n) # 숫자는 숫자형으로 변환
if cmd == "I":
heapq.heappush(min_q, (n, i))
heapq.heappush(max_q, (-n,i))
valid[i] = True
elif cmd == "D":
if n == 1:
if max_q and not valid[max_q[0][1]]: # max_q가 존재하고, 최댓값의 인덱스를 이미 사용했다면
heapq.heappop(max_q) # 버림
elif max_q and valid[max_q[0][1]]: # 살아있으면
valid[max_q[0][1]] = False
heapq.heappop(max_q) # 방문처리해주고 pop
elif n == -1:
if min_q and not valid[min_q[0][1]]:
heapq.heappop(min_q) # 한 번만 버림
elif min_q and valid[min_q[0][1]]:
valid[min_q[0][1]] = False
heapq.heappop(min_q)
# 마지막 정리
if max_q and not valid[max_q[0][1]]:
heapq.heappop(max_q)
if min_q and not valid[min_q[0][1]]:
heapq.heappop(min_q)
if not min_q or not max_q:
return [0, 0]
return [-max_q[0][0], min_q[0][0]]