hyunkookim 님의 블로그

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

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

703. Kth Largest Element in a Stream https://youtu.be/hOjcdrqMoQ8?si=j-8DMVDjR9t8bNx_ class KthLargest: def __init__(self, k: int, nums: List[int]): self.k = k self.minHeap = nums heapq.heapify(self.minHeap) # 최소 힙의 크기를 k 개로 유지하기 위한 로직 while len(self.minHeap) > k: # nums 리스트의 길이가 k보다 큰 경우, # 가장 작은 값을 하나씩 제거하여 힙의 크기를 k로 줄임 he..

90. Subsets II https://youtu.be/Vn2v6ajA7U0?si=w1awdAmx7zve9Tqv class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: # Sort the input list to group duplicates together # 입력 리스트를 정렬하여 중복된 숫자를 연속적으로 배치 nums.sort() # List to store all unique subsets # 모든 고유한 부분집합을 저장할 리스트 res = [] # Backtracking function # 백트래킹 함수 정..

78. Subsets https://youtu.be/REOH22Xwdkk?si=J1EDs8ppnu7DJndK class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: # subset 만들기 res = [] subset = [] def dfs(idx): if idx >= len(nums): print(idx, subset) res.append(subset.copy()) return # decision to include nums[idx] sub..

102. Binary Tree Level Order Traversal # 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: # root 없으면 return [] res = [] q = deque([r..

94. Binary Tree Inorder Traversal # 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: # inorder: dfs 에서,.. 왼쪽, 현재, 오른쪽 순회 # dfs 니깐, stack 이나 재귀로 if not root:..