Daniel's blog

가장 간단한 구현은 두 개의 array(list)를 첫 번째 array인 nums1으로 합친 후 정렬을 해주면 된다. 이 때는 시간 복잡도가 O (n log n) 이지만, Two Pointers (투 포인터)를 활용하면 O (n) 으로 두 개의 index를 각각 두고 각각의 element (요소)를 비교해가며 정렬된 array로 만들면 더 빠르게 구현이 가능하다. 1. 시간 복잡도: O (n log n) class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: for i in range(n): nums1[m+i] = nums2[i] nums1.sort() 2. 시간 복잡도: O (n) class ..

26번 문제와 마찬가지로 in-place 즉, input으로 주어진 nums를 직접 변경해야한다. val과 같은 값의 element가 주어지면 del 을 통해 하나씩 삭제해 나가면 정답을 어렵지 않게 구현할 수 있다. class Solution: def removeElement(self, nums: List[int], val: int) -> int: i = 0 while i < len(nums): if nums[i] == val: del nums[i] else: i += 1 return len(nums)

in-place 즉, input으로 주어진 nums의 값을 변경해야하는 것이 중요한 포인트 중 하나다. unique한 element를 집어주는 index (i)가 필요하고, 전제 nums에서 어디까지 진행했는지를 추적해주는 또 다른 index (j)를 두고 nums의 길이만큼 반복문을 실행하면 어렵지 않게 구현이 가능하다. class Solution: def removeDuplicates(self, nums: List[int]) -> int: if not nums: return 0 i = 0 for j in range(1, len(nums)): print(i, j, nums[i], nums[j], nums) if nums[j] != nums[i]: i += 1 nums[i] = nums[j] return..

input으로 주어진 두 스케쥴을 첫번째 요소의 크기를 기준으로 오름차순으로 정렬 후 각각에 index를 부여했다. 시작 시간은 비교 중인 두 slot 중 큰 값을, 끝나는 시간은 작은 값을 계산해 공통되는 구간을 찾고 해당 구간의 크기가 duration보다 길면 충분히 겹치는 시간이 있기에 반환한다. 스케쥴의 각 slot에서 두번째 요소인 끝나는 시간을 기준으로 index를 증가시켜 나갔다. class Solution: def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]: slots1.sort() slots2.sort() i = j = 0 while i < le..

inorder를 통해 BST를 traverse하면서 list에 오름차순으로 값을 넣고, 첫번째 list는 작은 숫자부터, 두번째 list는 큰 숫자부터 더하는 Two Pointer 방식으로 target을 찾았고 없으면 False를 반환한다. class Solution: def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool: def inorder(n): if n == None: return [] left = [] right = [] if n.left != None: left = inorder(n.left) if n.right != None: right = inorder(n.right) re..

Input으로 주어진 s가 또 다른 input인 t의 subsequence(연속이 아니더라도 포함이 돼있다면)인지 True/False를 반환하면 된다. 순서를 지켜야하기 때문에 sorting이나 hash map을 사용하는 것이 아니라 index를 이용해 비교해 나가는 방식으로 풀었다. Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing t..