hyunkookim 님의 블로그

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 최종 코드 class Solution: def search(self, nums: List[int], target: int)..

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

Time complexity 시간 복잡도   class Pair: def __init__(self, key, val): self.key = key self.val = valclass HashMap: def __init__(self): self.size = 0 self.capacity = 2 self.map = [None, None] def hash(self, key): index = 0 for c in key: index += ord(c) return index % self.capacity def get(self, key): index = sel..

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

1046. Last Stone Weight https://youtu.be/B-QCq79-Vfw?si=3xrwdkwlsVfUMrM8 class Solution: def lastStoneWeight(self, stones: List[int]) -> int: # 기본적으로 minHeap 이니깐, -1 곱하면 maxheap stones = [-s for s in stones] heapq.heapify(stones) print(stones) while len(stones) > 1: high_1st = heapq.heappop(stones) high_2nd = heapq.heappop(stones) ..