hyunkookim 님의 블로그

216. Combination Sum III class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: def backtrack(start, path, target): """ 백트래킹 함수 :param start: 탐색을 시작할 숫자 :param path: 현재까지 선택된 숫자의 리스트 :param target: 남은 목표 합 """ # 1. base case: 조건을 만족하는 경우 결과에 추가 if len(path) == k and ta..

2300. Successful Pairs of Spells and Potions https://youtu.be/OKnm5oyAhWg?si=k_d-0f6Nt10xOCD6 class Solution: def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]: # spell * potion >= success 를 만족하는 쌍을 찾아야 함 # 이를 변형하면: potion >= success / spell 이 됨 # 즉, potion의 값이 특정 기준값 이상인 경우를 찾아야 함. # 1. potions 리스트를 정렬하여 이진 탐색을 수행 가능하도록 준비..

2462. Total Cost to Hire K Workers class Solution: def totalCost(self, costs: List[int], k: int, candidates: int) -> int: n = len(costs) # 근로자의 총 수 # **교차점 처리**: # 만약 앞부분(pre)과 뒷부분(suf)이 겹치는 경우: # 전체를 정렬한 뒤, k명의 최소 비용을 더한 값을 반환. if 2 * candidates + k > n: costs.sort() # 비용 정렬 return sum(costs[:k]) # k개의 최소값을 반환 # **초기화..

2542. Maximum Subsequence Score class Solution: def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int: pairs = [(n1, n2) for n1, n2 in zip(nums1, nums2)] pairs = sorted(pairs, key=lambda p: p[1], reverse=True) minHeap = [] n1Sum = 0 res = 0 for n1, n2 in pairs: n1Sum +=n1 heapq.heappush(minHeap, n1) if ..

1926. Nearest Exit from Entrance in Maze # 최단거리 => BFS => queue # 시작점을 que 에 넣고. pop 하면서 검색 # pop 할때마다. 4방향 검색: 1레벨 up # 방문 셀 체크 해야함  https://youtu.be/fCfjOdi6V3g?si=RKIvqX7H_LOurZrM class Solution: def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int: # 최단거리 => buffer search => queue # 시작점을 que 에 넣고. pop 하면서 검색 # pop 할때마다. 4방향 검색: 1레벨 up # 방문 셀..

2336. Smallest Number in Infinite Set class SmallestInfiniteSet: def __init__(self): self.res = [True] * 1001 def popSmallest(self) -> int: for i in range(1, len(self.res)): if self.res[i] == True: self.res[i] = False return i def addBack(self, num: int) -> None: self.res[num] = True # Your SmallestInfi..

215. Kth Largest Element in an Array 정렬로 푸는 법class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: nums.sort() return nums[-k] 정렬 하지 않고 푸는 법- Heap / Priority Queue 사용 - 힙 큐, 우선순위 큐 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heap = [] for n in nums: heapq.heappush(heap, -n) # - 붙임으로써 큰->작은순으로 정렬 ..

1466. Reorder Routes to Make All Paths Lead to the City Zero GPT 풀이로 이해 감 BFSfrom collections import defaultdict, dequeclass Solution: def minReorder(self, n: int, connections: List[List[int]]) -> int: graph = defaultdict(list) for src, dst in connections: graph[src].append((dst, 1)) # 정방향 graph[dst].append((src, -1)) # 역방향 # BFS 탐색 visited..

841. Keys and Rooms - 꼭 방문 순서가, 순차적일 필요는 없고. - 방문 한 방 개수 == 방 개수 의 로직으로 출어야 함- DFS로.. => queue 사용class Solution: def canVisitAllRooms(self, rooms: List[List[int]]) -> bool: visited = set() que = deque([0]) while que: cur_room = que.popleft() if cur_room in visited: continue visited.add(cur_room) for k ..

1161. Maximum Level Sum of a Binary Tree # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def maxLevelSum(self, root: Optional[TreeNode]) -> int: if not root: return level = 1 max_level = 1 max_s..