백준 11279번 바로가기 나의 풀이 # 입력 import heapq n,*l = open(0) heap = [] # 처리 for x in l: if (x:=(-int(x))) == 0: try: print(-heapq.heappop(heap)) except: print(0) else: heapq.heappush(heap,x) CODE REVIEW python에서 제공하는 heapq - 힙 큐 알고리즘을 이용. 참고로 heapq 모듈의 documentation에 등장하는 관련 method는 다음과 같다 삽입: heapq.heappush(heap, item) 삭제: heapq.heappop(item) 만일 힙이 비어있으면 IndexError 발생. 문제는 heapq 모듈은 최솟값, 즉 min heap만 다룰 수 있다는 점인데, 이를 해결하기 위해 입력 받는 x의 부호를 (-)로 바꾸어 반전시켜서 heapq을 이용했다.
백준 11286번 바로가기 나의 풀이 # 입력 import sys import heapq n = int(sys.stdin.readline().strip()) heap = [] # 처리 for x in sys.stdin: if (x := (int(x))) == 0: try: print(heapq.heappop(heap)[1]) except: print(0) else: heapq.heappush(heap, (abs(x), x)) CODE REVIEW 11279번 - 최대 힙 & 1927번 - 최소 힙과 매우 유사한 문제. heapq로 절댓값 힙을 구현하기 위해서 heapq.heappush() 해줄 때에 (x의 절댓값, x)을 함께 넣어주었다. 정렬은 x의 절댓값으로 되고, 출력은 heappop()했을 때에 index 1인 요소를 출력해주면 된다.
백준 1927번 바로가기 첫 번째 시도 # 입력 import sys read = sys.stdin.readline n = int(read().strip()) arr = [] # 처리 for _ in range(n): x = int(read().strip()) if x == 0: try: print(arr.pop()) except: print(0) else: arr.append(x) arr.sort(reverse=True) 최종 제출 # 입력 import heapq n,*l = open(0) heap = [] # 처리 for x in l: if (x:=int(x)) == 0: try: print(heapq.heappop(heap)) except: print(0) else: heapq.heappush(heap,x) CODE REVIEW 자료구조와 우선순위 큐의 구현 방법에 따른 시간 복잡도는 링크 참조! 우선순위 큐를 구현하는 방법에는 여러가지가 있는데, 배열이나 연결 리스트를 이용할 경우 시간 복잡도가 (삽입,삭제) = (O(1),O(n)) 혹은 (O(n),O(1))로 나타난다. 삽입, 삭제를 모두 구현해야하는 이 문제에서는 O(n)의 시간복잡도는 시간초과 에러를 발생시킬 수 밖에 없다. 게다가 매번 x가 들어올 때마다 arr을 새로 정렬하니까 시간이 많이 걸릴 수 밖에.. 삽입할 때 오름차순을 헤치지 않는 알맞은 자리에 집어넣어야 시간을 절약할 수 있다. 따라서 삽입, 삭제 모두 시간복잡도가 O(logn)인 힙(heap)을 이용해서 우선순위 큐(priority queue)를 구현해보자. 힙(heap)을 스스로 구현하려다가 귀찮아서(…) 그냥 python에서 제공하는 heapq - 힙 큐 알고리즘을 이용했다. heapq 모듈의 documentation에 따르면… 삽입: heapq.heappush(heap, item) 삭제: heapq.heappop(item) 만일 힙이 비어있으면 IndexError 발생. heapq라는 매우 유용한 python 내장 모듈이 있음을 기억해두고, 최댓값/최솟값을 다루는 문제가 있다면 유용하게 써먹자!!