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..

거듭제곱 함수를 직접 구현하는 방법을 생각해보는 건 의미있다고 생각하지만, Constraints 때문에 오랜 시간이 걸렸다. 특히 Test Case를 생성해 확인해보는 과정 중에 'expected 'x^n' to have value from -10000 to 10000 only'라는 에러가 여러번 나왔는데 말 그대로 x^n이 10^4을 넘거나 -10^4 이하가 되지 않는다는 의미다. 이외에 문제를 구현하는 과정에 고민해볼 부분은 Time Limit Exceeded다. n이 매우 클 수 있기 때문에 O(n)으로 구혀하는 것은 시간 복잡도 측면에서 매우 좋지 못하다. 이진법을 활용해 구현하면 O(log n)으로 구현이 가능하다. 곱해야하는 수 x를 자리수가 늘어날 때마다 x를 계속 곱해 구현이 가능하다. e..

다른 함수들은 모두 간단히 구현이 가능하지만 top을 어떻게 구현하느냐에 따라 효율이 달라진다. list를 heap로 구성하는 heapify를 통해 max heap을 구현후 하나씩 pop하는 방식을 활용해 K개의 가장 높은 점수를 더해 반환했다. import heapq class Leaderboard: def __init__(self): self.dic = defaultdict(int) def addScore(self, playerId: int, score: int) -> None: self.dic[playerId] += score def top(self, K: int) -> int: ret = 0 values = list(self.dic.values()) n_values = [-val for val i..

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..

조건을 확인하는 WHERE에서 %를 연산해 조건에 해당하는 column을 뽑아내고 problem_id를 통해 정렬했다. SELECT problem_id FROM Problems WHERE likes / (likes + dislikes) * 100 < 60 ORDER BY problem_id 참고 - https://leetcode.com/problems/low-quality-problems/

input으로 주어진 num의 각 자리의 숫자를 나머지 연산자와 나누기를 통해 list에 저장하고, 이를 하나씩 꺼내 num이 나누어 떨어지면 카운트를 더해 반환했다. class Solution: def countDigits(self, num: int) -> int: ret = 0 n = num nums = [] while n > 0: nums.append(n % 10) n //= 10 for n in nums: if num % n == 0: ret += 1 return ret 참고: - https://leetcode.com/problems/count-the-digits-that-divide-a-number/

integer로 구성된 sticks라는 input array의 모든 요소를 이어 붙이는 문제다. 이 때 더할 때 마다 발생하는 합이 최소가 되도록 하는 문제다. sorting을 통해 풀이를 해야하나 잠시 생각했지만 Min heap을 사용하면 쉽게 구현이 가능하다. class Solution: def connectSticks(self, sticks: List[int]) -> int: mh = sticks ret = 0 heapify(mh) while len(mh) > 1: m1 = heappop(mh) m2 = heappop(mh) sum_ = m1 + m2 ret += sum_ heappush(mh, sum_) return ret