문제https://leetcode.com/problems/delete-greatest-value-in-each-row/ 해설2차원 상태의 배열에서 최대 힙을 적용하는 문제이다. Solution 1.아래는 heap을 이용하여 해결한 방식이다. import heapqclass Solution: def deleteGreatestValue(self, grid: List[List[int]]) -> int: answer = 0 while len(grid[0]) != 0: matrix = [] deleted_comp = [] for row in grid: row = [c if c Solution 2..
문제https://leetcode.com/problems/take-gifts-from-the-richest-pile/description/ 해설최대 힙을 이용하는 문제였다. import heapqclass Solution: def pickGifts(self, gifts: List[int], k: int) -> int: heap = [-v for v in gifts] heapq.heapify(heap) for _ in range(k): heapq.heapreplace(heap, -int((-heap[0]) ** 0.5)) return -sum(heap)
문제https://www.acmicpc.net/problem/19638 해설최대 힙을 사용하는 문제였다. # PyPy3import heapqdef solution(target, cnt, heap): heapq.heapify(heap) hammer_cnt = 0 for _ in range(cnt): height = -heap[0] if height == 1 or height
문제https://www.acmicpc.net/problem/2075 해설최소 힙을 사용하여 해결하는 문제이다. 공간복잡도를 고려해야하는 문제이므로 모든 데이터를 입력받은 후 pop을 진행하는 것이 아닌 input 과정 중 필요한 공간만큼만 사용하는 것이 핵심이었다. # PyPy3import heapqdef solution(cnt): heap = [] for _ in range(cnt): for v in list(map(int, input().split())): heapq.heappush(heap, v) if len(heap) == cnt+1: heapq.heappop(heap) return heapq.heap..
문제https://www.acmicpc.net/problem/1927 해설최소 힙(Min Heap)을 이용하여 해결하는 문제였다. Heap은 기본적으로 이진트리 구조로 형성되므로 insert와 delete 연산의 시간 복잡도는 \( O(logn) \)이 된다. 여기서 \( log \)는 일반적으로 밑이 2인 로그로 \( log_{2}{n} \)를 얘기한다. 이 문제에서는 입력 횟수만큼 반복하므로 \( O(Nlogn) \)이 된다. 패키지를 사용하여 해결하는 방법과 직접 구현 두 가지 방식으로 풀어보았다. 이번에도 input() 메소드가 시간초과를 유발하여 PyPy3를 이용하였다. Solution 1.아래는 heap을 이용하여 해결한 방식이다. # PyPy3import heapqdef solution(l..
문제https://www.acmicpc.net/problem/26042 해설로직은 단순했지만 기존 input() 메소드 사용에서 시간초과가 발생하였다. 패키지 import 없이 모든걸 해결해보려 했는데 결국 한계가 있을 수 있을 것 같다. 이번엔 PyPy3를 사용하여 해결하였다. # Python만 사용시 아래 메소드 사용 필요# input = __import__('sys').stdin.readline# PyPy3def solution(lst): max_cnt = -1 last_student = -1 queue = [] for v in lst: if v[0] == 1: queue.append(v[-1]) if max_cnt == le..
