서랍장

1060. Missing Element in Sorted Array n = [1, 2, 4], k = 3일 때를 생각해보면 좋다. class Solution: def missingElement(self, nums: List[int], k: int) -> int: missing = lambda idx: nums[idx] - nums[0] - idx n = len(nums) # for the case [1, 2, 4] # 4 + 3 - 1 = 6 if k > missing(n-1): return nums[-1] + k - missing(n-1) idx = 1 while missing(idx) < k: idx += 1 return nums[idx-1] + k - missing(idx-1) binary sera..

Rotate Array, 문제는 정말 간단하다. 그렇지만 시간복잡도를 O(1)으로 풀기 위해서는 약간의 아이디어가 필요한데, 배열의 item 값을 바꿀 때, item을 가르키는 prev을 지정해야하고, cnt로 전체 item을 탐색하고 있는지 추적해야한다. start는 n//k값이다. class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) k %= n # start defines start = cnt = 0 while cnt < n: # prev는 바뀌기 이전의 value를 지정 curr, prev = st..

1239. Maximum Length of a Concatenated String with Unique Characters backtracking이랑, 이중 for문 2가지로 해결할 수 있다. 1. 백트래킹 class Solution: def maxLength(self, arr: List[str]) -> int: self.maxLength = 0 # s is 현재까지의 문자열 # 탐색하는 문자열의 idx def backtrack(s, j): if len(s) != len(set(s)): return self.maxLength = max(len(s), self.maxLength) for idx in range(j, len(arr)): backtrack(s + arr[idx], idx) backtrack('..