#Array #DFS #BFS #Matrix URL Flood Fill - LeetCode Intuition Solution 1. Stack으로 DFS를 구현 Review Notes DFS(깊이 우선 탐색) 모든 경우 탐색, 순열, 조합, 가지치기 문제 재귀 또는 스택으로 구현 가능 BFS(넓이 우선 탐색) 최단 경로를 찾는 문제 큐로 구현 Solution class Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]: visited = [[False for _ in range(len(image[0]))] for _ in range(len(image))] stack = [(..
#Array #Binary_Search URL Binary Search - LeetCode Intuition start, middle, end 포인터를 사용하여 Binary Search를 진행한다. str으로 바꿔서 find함수를 써보려 했는데 마이너스 기호 때문에 불가능하다. Solution class Solution: def search(self, nums: List[int], target: int) -> int: start, end = 0, len(nums) while start < end: middle = (start+end)//2 if nums[middle] == target: return middle elif nums[middle] < target: start = middle + 1 else:..
#Hash_Table #String #Sorting URL LeetCode - The World's Leading Online Programming Learning Platform Intuition Solution 1: count 함수로 알파벳 수 세기 ⇒ Time Limit Exceeded class Solution: def isAnagram(self, s: str, t: str) -> bool: for c in s: if s.count(c) != t.count(c): return False s.replace(c, "") t.replace(c, "") return len(s) == len(t) Solution 2: sorting한 결과가 같은지 비교 Review Notes 문자열 정렬 s.sort()는..
#Binary_Tree #Recursion #BFS #DFS URL Invert Binary Tree - LeetCode Intuition Recursion 사용 Solution # 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 = right class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root is None: return None root.left, root.rig..
#Two_Pointers #String URL Valid Palindrome - LeetCode Intuition Solution 1: String을 반으로 잘라서 reverse한 후 같은지 확인 Solution 2: isalnum() 함수 사용, String을 반으로 자르지 않고 바로 비교 Solution 3: pointer를 사용해서 왼쪽 끝, 오른쪽 끝이 같은지 비교 (풀이 참고) Solution 4: Deque 사용 (풀이 참고) Review Notes String 뒤집기 s[::-1] 사용: 문자열 자르기와 함께 사용하면 결과가 이상하게 나옴 reversed(s) 사용: 결과를 join을 사용해서 다시 합쳐주어야 함 isalnum(): 알파벳 또는 숫자인 경우 True를 반환 성능 비교 Runt..
#Array #Dynamic Programming URL Best Time to Buy and Sell Stock - LeetCode Intuition Solution 1: for문 반복하면서 모든 profit을 계산한다. 그 중 max profit을 반환한다 ⇒ Time Limit Exceeded Solution 2: profit을 모두 계산하되, min_price와 profit을 swap하며 그때그때 최신 값으로 업데이트한다. min_price: 문제에서 price는 10000을 넘지 않는다고 하였으므로 초기값을 10000으로 두고 시작 Review Notes Time Limit Exceeded 코드 (실패) class Solution: def maxProfit(self, prices: List[in..
#Listed_Node #Recursion URL Merge Two Sorted Lists - LeetCode Intuition 처음에는 list1 자체를 수정하려고 했다.list2: 1 → 3 → 5인 경우 temp = list1 으로 temp 변수에 잠시 list1을 담아두고, list1 = list2 (즉, list1: 1→3→5) list1.next = temp (즉, list1: 1→2→4→6) list2 = list2.next (즉, list2: 3→5) list1 = list1.next 이런 식으로 하는 경우 list1의 포인터가 계속 바뀌어서 리스트노드의 첫 노드를 return할 수가 없었다. 현재 list1.val > list2.val 이므로 list1: 2 → 4 → 6 Review N..
#String #Stack URL Valid Parentheses - LeetCode Intuition Solution 1 여는 괄호(([{)인 경우: 일단 stack에 넣는다 닫는 괄호()]})인 경우 stack이 비었는데 닫는 괄호가 들어오면 return False stack.pop()을 했을 때 짝이 맞는 경우 stack의 마지막 요소와 짝이 맞지 않는 경우 이 과정이 끝났는데 stack이 비어있지 않은 경우: return False Review Notes Solution 2: dict를 사용한 정리된 코드(풀이 참고) Solution # Solution 1: 내 풀이 class Solution: def isValid(self, s: str) -> bool: stack = [] for char in..
#Hash_Table #Array URL Two Sum - LeetCode Intuition 방법 1: 이중 for문으로 가능한 모든 조합을 만든다 Review Notes 방법 2: (풀이 참고) x = target - nums[i]와 dictionary를 사용해서, dictionary에 x가 존재하는지 확인한다 Solution from typing import List # Solution 1 class Solution1: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i+1,len(nums)): if nums[i] + nums[j] == target: return [..
