hyunkookim 님의 블로그

286. Walls and Gates from collections import dequefrom typing import Listclass Solution: def wallsAndGates(self, rooms: List[List[int]]) -> None: """ Do not return anything, modify rooms in-place instead. """ """ 문제 설명: -1: 벽 또는 장애물로 이동 불가능한 위치를 나타냄 0: 게이트(문)가 있는 위치 INF (2147483647): 빈 공간으로, 게이트까지의 거리를 계산해야 함 목표: 각 빈 공간(21..

1091. Shortest Path in Binary Matrix 가장 짧은 경로 문제: BFS => 큐     cf) 목적지까지 갈수있는 경로 개수: DFS => 재귀 class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: N = len(grid) # n x n matrix if not grid: return -1 if grid[0][0] == 1 or grid[N-1][N-1] == 1: return -1 # shotedpath: using bfs, que def bfs(grid): q..

695. Max Area of Island BFS로 풀기from typing import Listfrom collections import dequeclass Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: # 섬 개수 및 최대 면적을 계산하는 함수 # Count the number of islands and calculate the maximum area # 네 방향 이동: 상, 하, 좌, 우 # Directions for movement: up, down, left, right directions = [[1, 0], [-1, 0], [0, 1], [..

981. Time Based Key-Value Store class TimeMap: def __init__(self): self.store = {} def set(self, key: str, value: str, timestamp: int) -> None: if key not in self.store: self.store[key] = [] self.store[key].append([timestamp, value]) # self.store[key].sort(key=lambda x: -x[0]) def get(self, key: str, timestamp: int) -> str: if key not in..

278. First Bad Version # The isBadVersion API is already defined for you.# def isBadVersion(version: int) -> bool:class Solution: def firstBadVersion(self, n: int) -> int: # 첫번째 bad 버전 찾기 # good, good, good, good, bad, bad, bad, .. 계속 bad l, r = 1, n while l

704. Binary Search class Solution: def search(self, nums: List[int], target: int) -> int: def bst(l, r): while l target: r =mid -1 else: return mid return -1 return bst(0, len(nums)-1) https://youtu.be/s4DPM8ct1pI?si=E2bD8-D_rcUUtBXz

217. Contains Duplicate class Solution: def containsDuplicate(self, nums: List[int]) -> bool: hashmap = {} for num in nums: if num not in hashmap: hashmap[num]=1 else: hashmap[num] += 1 return True return False

621. Task Scheduler class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: # each task takes 1 unit of time # minimize idle time # 각 작업은 1 단위 시간만 소요되며, 유휴 시간을 최소화하는 것이 목표 # Count the frequency of each task # 각 작업의 빈도를 세어서 저장 count = Counter(tasks) # 예: {"A": 3, "B": 3, "C": 1} # Convert the task counts to a max heap (negativ..

215. Kth Largest Element in an Array class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # minheap 으로 만들고, k개 까지. 힙 개수 유지하게 하면, # k 개 보다 많으면 작은 것들 제거 # 그렇게 하면, minheap[0]에는 k번째 큰 것이 남아있음 heapq.heapify(nums) while( len(nums) > k): heapq.heappop(nums) return nums[0] 메모리 절약을 위해, k 개 만큼 우선 넣어서, minheap 만들고.1개씩 추가해서, k개 넘는..

973. K Closest Points to Origin https://youtu.be/rI2EBUEMfTk?si=rQzq5oqyjL2M1qgb class Solution: def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]: # k번째 가까운 points 리턴, # [distance, x, y] 로 저장 # minHeap 사용 minHeap = [] for x, y in points: dist = (x**2) + (y**2) minHeap.append([dist, x, y]) heapq.heapify(minHe..