Daniel's blog

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

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

조건을 확인하는 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/

알파벳 26개로 구성된 keyboard String이 input으로 주어지고 0부터 25까지를 개개의 index로 간주하고, Hash map의 key로 keyboard의 각 character를 value로 넣은 후, 또 다른 input인 word의 character를 앞에서 하나씩 읽어들여 각각을 Hash map의 key로서 value를 찾는다. 그리고 차이(절대값)의 누적합을 반환했다. class Solution: def calculateTime(self, keyboard: str, word: str) -> int: dic = {} p = 0 ret = 0 for i, k in enumerate(keyboard): dic[k] = i for i, w in enumerate(word): ret += ab..

class Solution: def minSwaps(self, data: List[int]) -> int: ret = ones = 0 for i, d in enumerate(data): if d == 1: ones += 1 for i in range(ones): if data[i] == 0: ret += 1 cnt = ret for i in range(ones, len(data)): if data[i-ones] == 0: cnt -= 1 if data[i] == 0: cnt += 1 ret = min(ret, cnt) return ret 0과 1로 이뤄진 'data'라는 binary array가 input으로 주어질 때 모든 1이 연속하도록 그룹을 지을 때 최소로 swap하는 수를 반환하는 문제다. Tw..

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

'169. Majority Element'에서 난이도가 조금 올라간 문제지만 큰 틀에선 똑같기에 솔루션 역시 흡사하다. Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. Example 1: Input: nums = [3,2,3] Output: [3] Example 2: Input: nums = [1] Output: [1] class Solution: def majorityElement(self, nums: List[int]) -> List[int]: dic = defaultdict(int) for i, n in enumerate(nums): dic[n] += 1 ret = [] for i, k i..

1150번과 매우 유사한 문제다. 다만 다른 점은 해당 문제에선 Majority Element가 반드시 있다는 가정하에 이를 반환하는 것이고, 1150은 input으로 주어진 숫자가 Majority Element가 맞는지 틀린지를 반환하는 것이다. Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1: Input: nums = [3,2,3] Output: 3 Example 2: In..