코딩

정답) class Solution: def isPalindrome(self, s: str) -> bool: left = 0 right = len(s)-1 while left < right: if s[right].isalnum() and s[left].isalnum(): if s[right].lower() != s[left].lower(): return False left += 1 right -= 1 elif not s[left].isalnum(): left += 1 elif not s[right].isalnum(): right -= 1 return True 문제) 문제 출처 팰린드롬 (회문)은 거꾸로 읽어도 똑같은 문장을 뜻합니다. 이 문제에서는 대문자들을 전부 소문자 취급하고 알파벳과 숫자를 제외한 문..

정답) class Solution: def maxProfit(self, prices: List[int]) -> int: # 0번째 가격을 저장 buy = prices[0] profit = 0 for i in range(1, len(prices)): # 만약 다른 가격이 더 비싸다면 현재 수익과 비교 후 # 현재 수익보다 더 크다면 profit을 업데이트 if prices[i] > buy: profit = max(prices[i] - buy, profit) # 만약 다른 가격이 더 싸다면 사는 가격을 업데이트 else: buy = prices[i] return profit 문제) 문제출처 i번째 날의 주식 가격을 알려주는 배열 prices가 주어집니다. 당신은 하루를 정해 주식은 산 이후 미래에 팔아 최대..

정답) class Solution: def generate(self, numRows: int) -> List[List[int]]: # 규칙성이 없어 그냥 리턴하는 경우 if numRows == 1: return [[1]] if numRows == 2: return [[1], [1, 1]] # 초기 세팅 res = [[1], [1, 1]] # Recursive Function def helper(res, num): # Base Case if num < 3: return # Recursive Call helper(res, num-1) # 새로운 리스트 만드는 과정 start = [1] for i in range(num-2): start.append(res[-1][i] + res[-1][i+1]) start...

정답) class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: # Recrusive Func def helper(l, r): # Base Case if l > r: return None # Recursive Calls m = (l+r) // 2 root = TreeNode(nums[m]) root.left = helper(l, m-1) root.right = helper(m+1, r) return root return helper(0, len(nums)-1) 정답출처: NeetCode 문제) 문제출처 정수 배열 nums는 오름차순으로 정렬되어 있습니다. 이 배열을 height balanced BST(Binary ..

정답) class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: # Recursive 함수 def helper(root): # Base Case if not root: return 0 # Recursive Calls # root의 왼쪽 subtree의 depth를 구해줌 count1 = helper(root.left) # root의 오른쪽 subtree의 depth를 구해줌 count2 = helper(root.right) # 왼쪽/오른쪽 sub tree 중 더 깊은 트리와 루트 노드 1개를 합쳐 리턴 return max(count1, count2) + 1 return helper(root) 문제) 문제출처 Binary Tree의 루트가 ..

정답) class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: # Recursive Function def helper(leftRoot, rightRoot): # Base Case if not leftRoot and not rightRoot: return True # 두 노드가 둘 다 존재해 비교가 가능할 때 if leftRoot and rightRoot: # left의 left와 right의 right을 비교한 결과를 저장 res1 = helper(leftRoot.left, rightRoot.right) # left의 right과 right의 left를 비교한 결과를 저장 res2 = helper(leftRoot.right, r..

정답) class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: # inorder traversal하며 값을 넣을 공간 res = [] # res에 넣어줄 nested recursive func def inorder(root): if not root: return inorder(root.left) res.append(root.val) inorder(root.right) # recursive func 실행 inorder(root) return res 자료참고: NeetCode 문제) 문제출처 BInary tree의 루트가 주어졌을 때, inorder traversal한 노드들의 값을 리턴하시오. 예시 1) root ..

정답) class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: # nums1을 선형할 인덱스 i = m - 1 # nuns2를 선형할 인덱스 j = n - 1 # nums1에 새롭게 추가될 자리의 인덱스 k = m + n - 1 # nums1과 nums2 모두 선형할 원소가 존재할 때 while i >= 0 and j >= 0: if nums2[j] > nums1[i]: nums1[k] = nums2[j] j -= 1 # nums2[j] = 0: nums1[k] = nums2[j] j -= 1 k -= 1 참고자료: PratikSen07 문제) 문제출처 오름차 순으로 정렬된 정수 배열 nums1..

정답) class Solution: def climbStairs(self, n: int) -> int: # 동적 계획법 # 바텀업 DP 테이블 dpTable = [1, 1] for i in range(n-1): # 테이블에 n-1, n-2번째 피보나치 숫자들을 더해 추가 dpTable.append(dpTable[-1] + dpTable[-2]) return dpTable[-1] 참고자료: NeetCode, 앎의 공간 문제) 문제출처 정상까지 n번 만큼 걸어야되는 계단이 있습니다. 이 계단을 오르기 위해서 한번에 1번 또는 2번의 걸음으로 오를 수 있습니다. 총 몇가지의 방법으로 이 계단을 오를 수 있습니까? 예시 1) n = 2 output = 2 1. 1+1 1. 2 예시 2) n = 3 output ..

정답) class Solution: def mySqrt(self, x: int) -> int: # x가 0, 1일 때는 제곱근 또한 0, 1 if x < 2: return x left = 1 right = x # 이진검색 while left