hyunkookim 님의 블로그

232. Implement Queue using Stacks 이 문제는 두 개의 스택을 이용해서 큐(FIFO)를 구현하는 문제로, 인터뷰에서도 자주 나오는 고전 문제입니다.Follow-up 조건인 "모든 연산의 시간복잡도가 평균 O(1)" 도 만족해야 합니다.✅ 핵심 아이디어두 개의 스택 사용:in_stack: push() 할 때 사용하는 스택 (뒤쪽에 쌓임)out_stack: pop()/peek() 할 때 사용하는 스택 (앞쪽에서 꺼냄)📌 필요할 때만 in_stack을 out_stack으로 옮기기 때문에 amortized O(1) 시간 보장됨✅ 구현 코드 (Python, 리스트를 스택처럼 사용)class MyQueue: def __init__(self): # 데이터를 입력받는 스택 ..

141. Linked List Cycle# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: # 링크드리스트에서 싸이클있는지 보려면, fast(두칸씩) 와 slow(한칸씩)가 만나는지 보면 됨 slow = fast = head while slow and fast: if slow == fast: return True ..

110. Balanced Binary Tree✅ 정답 접근 방식모든 서브트리에서 좌우 높이 차가 1 이하여야 함재귀적으로 하향하면서, 각 노드의 서브트리 균형 여부까지 함께 체크해야 함보통은 dfs() 함수에서 높이(height)를 리턴하면서, 불균형이면 특수값(-1 등)을 리턴하는 방식이 깔끔해요최종 코드🔧 정답 코드 (DFS 방식, 높이와 균형 여부 동시에 판단)# 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..

235. Lowest Common Ancestor of a Binary Search Tree # Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': # 바이너리 서치 트리 BST 에서 가장 가까운 조상 찾기 # BST 이므로, 왼쪽에 있으면 무조건 작은값, 오른..

733. Flood Fill class Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]: # (sr, sc) 시작으로. color 로 바꾸면 됨 # 4방향으로 확산 => BFS => 큐 사용 rows, cols = len(image), len(image[0]) visited = set() q = deque([(sr, sc)]) visited.add((sr, sc)) start_val = image[sr][sc] while q: r, ..

704. Binary Search class Solution: def search(self, nums: List[int], target: int) -> int: # ascending order: 증가..숫자 순서 # target 찾으면 return index 아니면, -1 l, r = 0, len(nums)-1 """ '==' 꼭 있어야 함, l>r 일때만 나와야 함. """ while lclass Solution: def search(self, nums: List[int], target: int) -> int: # 이진트리로 검색 l, r = 0, len(nums)-1 ..

242. Valid Anagramclass Solution: def isAnagram(self, s: str, t: str) -> bool: # t 가 s의 anagram 이면 return True # An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once. # 문자와 각 문자의 개수가 같으면 anagram def getStrCountChar(strs): countChar = {} for s in strs: ..

226. Invert 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None # 현재 왼, 오 바꾸고 tmp = root.left root...

125. Valid Palindromeclass Solution: def isPalindrome(self, s: str) -> bool: # Palindrome: 앞으로 읽으나, 뒤로 읽으나 똑같으면 # 모든 Alphanumeric character 만 남기고: 글자와 숫자 # 모든 글자 소문자로.. all_alphanumeric_char = "0123456789abcdefghijklmnopqrstuvwxyz" all_alphanumeric_char_no_blank = "" for w in s.lower(): if w in all_alphanumeric_char: ..

121. Best Time to Buy and Sell Stock class Solution: def maxProfit(self, prices: List[int]) -> int: # 먼저 사고 팔수 있음 bestProfit = 0 lp = len(prices) for buy_i in range(lp-1): for sell_i in range(buy_i+1, lp): profit = prices[sell_i]-prices[buy_i] bestProfit = max(bestProfit, profit) return bestProfit Time Limit Exceeded지..