문제
https://programmers.co.kr/learn/courses/30/lessons/42628
풀이
힙 카테고리에 있어서 힙으로 만들어 풀어야겠다고 생각했다.
힙은 최소, 최대 힙 중 하나로 만들어져야 하는데 문제에서는 최대와 최소를 모두 삭제할 수 있어야 했다.
그래서 최대 힙, 최소 힙 총 2개를 만들고 만약 최대값 삭제 시 최대 힙의 값을 최소 힙에서 검색해서 삭제하는 방식으로 풀어야하나? 싶었는데 로직이 깔끔하지 못한 느낌이고 비효율적일 것 같았다.
이런저런 고민을 해보다가 그냥 힙 버리고 냅다 풀어보기로 했다.
def solution(operations):
q = []
for o in operations:
op = o.split()
if op[0] == 'I':
q.append(int(op[1]))
elif op[0] == 'D':
if len(q) == 0:
continue
elif op[1] == '1':
q.remove(max(q))
else:
q.remove(min(q))
return [max(q) if q else 0, min(q) if q else 0]
그런데 웬걸,, 효율성 테스트같은게 있을 줄 알았는데 그런거 없고 그냥 통과했다.
다른 사람의 풀이
분명 문제에서는 이걸 의도한 것이 아니었을 것 같았고 내 풀이는 실제 코테에선 통과하지 못할 것 같았다.
from heapq import heappush, heappop
def solution(arguments):
max_heap = []
min_heap = []
for arg in arguments:
if arg == "D 1":
if max_heap != []:
heappop(max_heap)
if max_heap == [] or -max_heap[0] < min_heap[0]:
min_heap = []
max_heap = []
elif arg == "D -1":
if min_heap != []:
heappop(min_heap)
if min_heap == [] or -max_heap[0] < min_heap[0]:
max_heap = []
min_heap = []
else:
num = int(arg[2:])
heappush(max_heap, -num)
heappush(min_heap, num)
if min_heap == []:
return [0, 0]
return [-heappop(max_heap), heappop(min_heap)]
내가 처음 생각했던 것처럼 max힙과 min 힙을 두개 만들어 연산한 코드이다.
그런데 두 힙의 동기화 과정이 없어 틀렸다는 말도 있다.
import heapq
def solution(operations):
heap = []
for operation in operations:
operator, operand = operation.split(' ')
operand = int(operand)
if operator == 'I':
heapq.heappush(heap, operand)
elif heap:
if operand < 0:
heapq.heappop(heap)
else:
heap.remove(max(heap))
if not heap:
return [0, 0]
return [max(heap), heap[0]]
다른 코드.
이건 최소힙을 만들고 최댓값은 remove로 제거했다.
다른 글에서는 heapq.nlargest(n, list)을 사용해 정렬하고 다시 최소힙을 만들기도 했다
뭔가 이거다 싶게 깔끔한 로직은 없었다.
애초에 효율성 테스트도 없는 문제라 그런가 싶다.
'알고리즘 스터디' 카테고리의 다른 글
[프로그래머스] DFS/BFS 4. 여행경로 (0) | 2021.08.20 |
---|---|
[프로그래머스] 탐욕법 6. 단속 카메라 (0) | 2021.08.07 |
[프로그래머스] 깊이/너비 우선 탐색 3. 단어 변환 (0) | 2021.07.25 |
[프로그래머스] 동적계획법 3. 등굣길 (0) | 2021.07.16 |
[프로그래머스] 탐욕법 5. 섬 연결하기 (1) | 2021.07.10 |