Scribbling

DP 기초 문제로 맨날 보는 문제 class Solution: def rob(self, nums: List[int]) -> int: if len(nums)

프로그래머스에도 있는 문제이다. 문제를 처음 봤을 때, 가장 먼저 nums를 정렬해야된다는 것을 알 것이다. 여기서 정렬을 어떻게 하는지가 핵심인데, 34343 과 3434 중 어느것이 먼저 나와야할지를 생각해보면 된다. 그냥 정렬한다면, 34343이 앞에 와버리는 문제가 있다. 34343+3434 반대의 경우는, 3434+34343 그러나 후자의 경우가 더 크다. 이를 검출할 수 있는 방법은 해당 숫자들을 반복시켜서 얻는 새로운 숫자열을 비교하는 것이다. 3434334343과 34343434 를 비교하면 된다. 아래 코드에서는 숫자를 10번 반복시키는데, 이는 숫자의 최대 길이가 10이기 때문이다. (1과 10000000000의 비교하는 경우) class Solution: def largestNumbe..

알고리즘 문제라고 하기도 애매한 것 같다. n! 결과값에서 맨 뒤에 놓이는 0의 갯수를 찾는 문제이다. 맨 뒤의 0의 갯수는 n!으로 만들 수 있는 10의 갯수와 동일한데, 10은 2*5이므로, 2*5가 몇 번 발생하는지 확인하면 된다. 2*5의 횟수는 다시 5의 횟수로 결정된다. (2는 흔하니까) class Solution: def trailingZeroes(self, n: int) -> int: ret = 0 x = 5 while n >= x: ret += n // x x *= 5 return ret

O(1) Memory로 어떻게 풀지 고민해보았다. 방법은 두 List의 node 갯수를 파악하는 것이다. # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: m, n = 0, 0 cur = headA while cur != None: m += 1 cur = cur.next cur = headB while cur != None: n += 1 cur = cur.next if m >= n: for..

Binary Search class Solution: def findPeakElement(self, nums: List[int]) -> int: INT_MAX = int(1e12) nums = [-INT_MAX] + nums + [-INT_MAX] def isPeak(idx): if nums[idx] > nums[idx-1] and nums[idx] > nums[idx+1]: return True return False left, right = 1, len(nums) - 2 while left nums[mid]: right = mid - 1 else: left = mid + 1

class MinStack: def __init__(self): self.stack = [] def push(self, val: int) -> None: if not self.stack: self.stack.append([val, val]) else: self.stack.append([val, min(val, self.stack[-1][1])]) def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1] # Your MinStack object will be instantiated and called as such: # ..

class Solution: def maxProduct(self, nums: List[int]) -> int: ret = -int(1e9) prod = 1 for num in nums: prod *= num ret = max(ret, prod) if num == 0: prod = 1 prod = 1 for i in range(len(nums)-1, -1, -1): prod *= nums[i] ret = max(ret, prod) if nums[i] == 0: prod = 1 return ret

class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: culsum = 0 for i in range(len(gas)): gas[i] -= cost[i] culsum += gas[i] if culsum < 0: return -1 start_idx, culsum = 0, 0 for i in range(len(gas)): culsum += gas[i] if culsum < 0: culsum = 0 start_idx = i + 1 return start_idx

stack을 사용 class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] predefined_tokens = ['+', '-', '*', '/'] operations = [lambda x, y : x + y, lambda x, y : x - y, lambda x, y : x * y, lambda x, y : int(x / y)] for token in tokens: if token in predefined_tokens: num2 = stack.pop() num1 = stack.pop() idx = predefined_tokens.index(token) stack.append(operations[idx](num1, num2)) els..

Relatively straightforward solution, O(N) time O(1) Memory. class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: numZero, prod, zeroidx = 0, 1, 0 for i, num in enumerate(nums): if num == 0: numZero += 1 zeroidx = i else: prod *= num if numZero >= 2: return [0] * len(nums) if numZero == 1: ret = [0] * len(nums) ret[zeroidx] = prod return ret # backward pass ret = [0] * len(n..