파이썬

정답) 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

정답) class Solution: def plusOne(self, digits: List[int]) -> List[int]: # 1의 자리에 1을 더함 digits[-1] += 1 # digits의 0번째 정수 제외 만약 i번째 정수가 10이면 # 0으로 바꿔주고 [i-1]에 더함 for i in range(len(digits)-1, 0, -1): if digits[i] == 10: digits[i] = 0 digits[i-1] += 1 # 만약 0번째 정수가 10이면 0으로 바꾸고 # 0번째 정수에 1을 새롭게 추가 if digits[0] == 10: digits[0] = 0 digits.insert(0, 1) return digits 문제) 주어진 리스트 digits는 정수가 자릿값에 따라 놓인 리..

정답) class Solution: def strStr(self, haystack: str, needle: str) -> int: # needle의 길이 만큼의 문자열을 haystack에서 검색 for i in range(len(haystack) - len(needle) + 1): # 그 문자열이 needle과 같다면 if haystack[i:i+len(needle)] == needle: return i return -1 문제) 문제출처 주어진 문자열 haystack과 needle을 사용하여, haystack에서 needle이 처음 발견되는 index를 리턴하거나 haystack에 needle이 존재하지 않는다면 -1을 리턴하시오. 예시 1) haystack = "sadbutsad", needle = "..

정답) class Solution: def removeDuplicates(self, nums: List[int]) -> int: # 딕셔너리의 key에 유니크한 정수를 저장 numDic = {nums[0]:1} k = 1 for i in range(1, len(nums)): # 만약 새로운 유니크한 정수가 발견되면 if nums[i] not in numDic: # 딕셔너리에 추가 numDic[nums[i]] = 1 # k에 1 더함 k += 1 # nums의 올바른 위치에 새로운 유니크한 정수 옮김 nums[k-1] = nums[i] return k 문제) 문제출처 주어진 정수 배열 nums는 오름차순으로 정렬되어 있습니다. 반복되는 정수를 제거하여 그 정수가 한 번만 나오도록 하시오. 원래 nums에 ..