hyunkookim 님의 블로그

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) # - 붙임으로써 큰->작은순으로 정렬 ..

399. Evaluate Division visited 변수를 dfs 생성 할때마다 생성 Runtime: 0ms, Beats100.00%Memory: 16.70MB, Beats49.42%from collections import defaultdict, dequeclass Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: # 1. 그래프 생성 adj = defaultdict(list) for (src, dst), val in zip(equations, values): adj[..

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..

547. Number of Provinces class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: # dfs 로.. # init n = len(isConnected) province = 0 visited = [False]*n def dfs(cur_node_number: int): visited[cur_node_number] = True for neighbor in range(n): if isConnected[cur_node_number][neighbor] == 1 and vi..

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..

199. Binary Tree Right Side View # 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: # return root, null 을 반환하면 안되고, []을 반환해야함 return [] ..

236. Lowest Common Ancestor of a Binary Tree LCA(최저 공통 조상) 찾기노드 자신도 공통조상이 될수 있음재귀로..일단 루트가 none 이면 return 또는 return root루트가 p 또는 q 인지 체크해서 맞으면 루트 반환아니면, ..class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root: # 빈 노드면 return ## return root if root == p or root == q: return root # 좌측에..