힙5 [백준] 7662번 - 이중 우선순위 큐 (파이썬) # 이중 우선순위 큐 import heapq T = int(input()) for _ in range(T): N = int(input()) min_heap = [] max_heap = [] visited = [False] * N for idx in range(N): order, data = input().split() data = int(data) if order == 'I': heapq.heappush(min_heap, (data, idx)) heapq.heappush(max_heap, (-data, idx)) visited[idx] = True elif order == 'D': if data == 1: while max_heap and not visited[max_heap[0][1]]: heapq.h.. 2022. 5. 17. [프로그래머스] 고득점Kit (3) - 힙 (파이썬) 1. 더 맵게 (Lv. 2) # 더 맵게 import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) while scoville[0] = 2: new = heapq.heappop(scoville) + (heapq.heappop(scoville)*2) heapq.heappush(scoville, new) answer += 1 else: answer = -1 break return answer scoville리스트를 heapq로 만들어준다. (heapq.hepify) 가장 작은 값(scoville[0])이 K보다 작으면 두 재료를 섞어서 새로운 스코빌 지수를 가진 재료를 scoville에 넣어 .. 2022. 3. 2. [백준] 2075번 - N번째 큰 수 ( 파이썬) # N번째 큰 수 import sys import heapq input = sys.stdin.readline N = int(input()) heap = [] for i in range(N): temp = list(map(int, input().split())) if i == 0: for x in temp: heapq.heappush(heap, x) continue for x in temp: if heap[0] < x: heapq.heappop(heap) heapq.heappush(heap, x) print(heap[0]) 힙 1. 한 줄씩 입력을 받고 첫 줄은 heapq에 push 2. 둘째 줄 부터는 - heap[0]보다 큰 수만 push - 이때, heap의 크기를 N만큼 유지해주기 위해서 pop 3.. 2022. 3. 2. [백준] 1202번 - 보석 도둑 (파이썬) # 보석 도둑 import sys import heapq input = sys.stdin.readline N, K = map(int, input().split()) gem = [] for _ in range(N): weight, cost = map(int, input().split()) heapq.heappush(gem, (weight, cost)) bags = [] for _ in range(K): w = int(input()) bags.append(w) bags.sort() result = 0 temp = [] for bag_weight in bags: while gem: if bag_weight >= gem[0][0]: weight, cost = heapq.heappop(gem) heapq.heap.. 2022. 1. 30. [백준] 1655번 - 가운데를 말해요 (파이썬) # 가운데를 말해요 import sys import heapq input = sys.stdin.readline N = int(input()) left = [] right = [] for _ in range(N): if len(left) == len(right): heapq.heappush(left, -int(input())) else: heapq.heappush(right, int(input())) if len(left) != 0 and len(right) != 0 and -left[0] > right[0]: add_left = heapq.heappop(right) add_right = heapq.heappop(left) heapq.heappush(left, -add_left) heapq.heappush.. 2022. 1. 26. 이전 1 다음
