🧑🏻‍💻 LeetCode Medium Collections 1 - 20 Problems

0300. Longest Increasing Subsequence / 0053. Maximum Subarray

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        length = len(nums)
        dp = [1]*length

        for x in range(1,length):
            for y in range(0,x):
                if nums[y] < nums[x]:
                    dp[x] = max(dp[x],dp[y]+1)
        return max(dp)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans,curmax=-10001,0
        for i in range(len(nums)):
            curmax=max(curmax+nums[i],nums[i])
            ans=max(ans,curmax)
        return ans

 

🧑🏻‍💻 300) 전형적 LIS 유형 문제. 위 코드는 O(n^2)으로 해결한 알고리즘이나, 이분탐색을 활용한 O(nlogn) 알고리즘 풀이도 가능하다.

 

🧑🏻‍💻 053) subarray의 연속된 부분합이 가장 클 때의 sum 값을 출력하는 문제. dp 또는 divide & conquer 기법 모두 사용 가능(위 풀이는 dp로 curmax를 O(n)으로 돌며 계속 업데이트)

---

0152. Maximum Product Subarray / 0198. House Robber

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        dp=(nums[0],nums[0])
        ans=nums[0]
        for i in range(1,len(nums)):
            dp=(max(dp[0]*nums[i],dp[1]*nums[i],nums[i]),min(dp[0]*nums[i],dp[1]*nums[i],nums[i]))
            ans = max(ans,max(dp))
        return ans

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp=(nums[0],0)
        for x in range(1,len(nums)):
            dp=(dp[1]+nums[x],max(dp))
        return max(dp)

 

🧑🏻‍💻 152) subarray의 합이 아닌 subarray의 product 최댓값을 구하는 문제. 배열에 0과 음수도 들어갈 수 있으므로, 음수와 음수를 곱하면 다시 양수로 바뀌어 큰 값으로 되기 때문에 dp-table의 tuple값을 현재의 최댓값과 최솟값 두 개 모두 update 해주어야 한다. 자기 자신 / 자기 자신과 앞 원소의 최댓값과의 곱 / 자기 자신과 앞 원소의 최솟값과의 곱 이렇게 3개 중 최댓값과 최솟값으로 update 필요

 

🧑🏻‍💻 198) 연속해서 집을 털 수 없으므로 띄어서 집을 털 경우 가져갈 수 있는 돈의 최댓값을 구해야 한다.

 

: 해당 원소를 포함하는 경우는, 앞선 dp 원소에서 포함하지 않은 경우 + 해당 원소 / 해당 원소를 포함하지 않는 경우는, 해당 원소 없이, 앞선 dp의 최댓값으로 업데이트 해주면 된다.

---

0238. Product of Array Except Self / 0098. Validate Binary Search Tree

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans=[]
        pre,after = [],[]
        pre_n,after_n=1,1
        for x in range(len(nums)):
            pre_n*=(nums[x])
            pre.append(pre_n)
            after_n*=(nums[len(nums)-1-x])
            after.append(after_n)
        a,b=-1,len(nums)-2
        for x in range(len(nums)):  
            if a < 0:
                ans.append(after[b])
            elif b < 0:
                ans.append(pre[a])
            else:
                ans.append(pre[a]*after[b])
            a+=1
            b-=1
        return ans

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def check(node, low=-float('inf'), high=float('inf')):
            if not node:
                return True
    
            if node.val <= low or node.val >= high:
                return False
    
            return (check(node.left, low, node.val) and check(node.right, node.val, high))
    
        return check(root)

 

🧑🏻‍💻 238) 현재 원소의 index가 x라면 (index 0 ~ (x-1)까지의 곱) x (index (x+1)부터 끝까지의 곱)을 각 원소마다 업데이트해주면 된다.

 

🧑🏻‍💻 098) 주어진 Tree가 Binary Search Tree를 만족하면서 valid BST인지까지 두 가지 조건을 만족시키는 지 확인하는 문제. valid BST란, head node가 있고 left 또는 right child가 있다면, 전체 tree의 모든 subtree가 left.val < head.val < right.val을 만족시키는 tree이다.

: 여기서 주의할 건, 전체 tree의 모든 subtree가 left.val < head.val < right.val을 만족시켜야 한다는 점. 아래 예시를 확인하자

: 초록색을 가리키는 sub-tree는 left.val < root.val < right.val 속성을 만족하는 tree이다. 하지만, 이보다 스케일이 더 큰 파란색 영역의 subtree를 보았을 때 root.val 33기준 4번 노드 val은 0번 노드 val 보다 크고, 5번 노드 val은 0번 노드 val 보다 작으므로 만족하지 않는다. 따라서, 모든 subtree에 대해 left.val < root.val < right.val 속성을 만족해야 한다.

 

: recursion 활용시 함수의 parameter 세 종류를 head node, 해당 head node를 head로 갖고 있는 subtree에서 head node 가능한 범위 최솟값-1, 최댓값+1 이렇게 설정. recursive하게 각 node를 돌며 각 node가 가능한 범위 최솟값과 최댓값 사이에 속하지 않으면 바로 False 리턴. 그렇지 않으면 해당 node의 left와 right 각각 head node로 두는 subtree recusive하게 돌려(left와 right 모두 만족하게 되므로 and 조건 연결) 계속 확인! (위 오른쪽 그림 참고)

---

0150. Evaluate Reverse Polish Notation / 0102. Binary Tree Level Order Traversal

import math
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack=[]
        operands=['*', '+', '-', '/']
        for token in tokens:
            if token not in operands:
                stack.append(int(token))
            else:
                x,y=stack.pop(),stack.pop()
                if token == '+':
                    stack.append(x+y)
                elif token == '-':
                    stack.append(y-x)
                elif token == '/':
                    stack.append(math.trunc(y/x))
                else: #*
                    stack.append(x*y)
        return stack[-1]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return None
        queue = deque([root])
        answer = []
        while queue:
            level = []
            length = len(queue)
            for _ in range(length):
                cur = queue.popleft()
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            answer.append(level)
        return answer

 

🧑🏻‍💻 0150) operand에 따라 최근에 들어온 두 개의 원소를 연산하는 전형적인 stack 문제. 예를 들어 3 4 + 라면, 숫자만 stack에 넣고, +와 같은 operand를 만났을 때 최근에 넣은 두 개를 빼서 operand에 따라 연산한 뒤, 다시 stack에 넣기를 반복. 이 때 나눗셈만 주의. 파이썬의 경우 / 연산자 사용하여 나누고, math.trunc() 함수(소수점 버리는 함수) 활용하여 연산

 

🧑🏻‍💻 0102) level order로 읽어서 level 별 node의 value를 한 개의 list로 만들고 전체 이중 list를 출력하는 문제. level별로 node를 읽으므로 BFS 활용. for문 내부에 print(root)를 넣는다면 아래와 같은 결과가 나온다.

즉 root의 길이 자체가 현 level의 node 개수이므로 length = len(queue)로 length만큼 popleft() 진행한 다음, for문 돌 때마다 level list에 node.val append. 최종적으로 level list를 계속 넣은 answer 2차원 list 출력

---

0133. Clone Graph / 0200. Number of Islands

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional
from collections import deque
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return
        clone = Node(node.val)
        clones = {node: clone}
        queue = deque([node])
        while queue:
            node = queue.popleft()
            for nei in node.neighbors:
                if nei not in clones:
                    clones[nei] = Node(nei.val)
                    queue.append(nei)
                clones[node].neighbors.append(clones[nei])
        return clone

from collections import deque
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def BFS(graph, start):
            graph[start[0]][start[1]] = '0'
            queue = deque([start])
            dx, dy = [-1,1,0,0], [0,0,-1,1]
            while queue:
                node = queue.popleft()
                for i in range(4):
                    nx, ny = node[0]+dx[i], node[1]+dy[i]
                    if 0<=nx<m and 0<=ny<n:
                        if graph[nx][ny] == '1':
                            graph[nx][ny] = '0'
                            queue.append((nx,ny))
        m, n = len(grid), len(grid[0])
        ans = 0
        for x in range(m):
            for y in range(n):
                if grid[x][y] == '1':
                    ans += 1
                    BFS(grid,(x,y))
        return ans

 

🧑🏻‍💻 0133) BFS

(1) 시작 node를 위한 clone Node class를 생성.

(2) 그 다음 queue에 넣고, BFS로 연결 노드 확인. 연결 노드 있을 때마다 기존 노드의 neighbors에 update

(3) 연결 노드가 clones에 없다면 연결 노드가 들어간 새로운 Node class 생성하고 clones dictionary에 생성한 Node class 삽입. queue에 append

(4) 위 (2) ~ (3) 과정 queue에 아무 것도 없을 때까지 반복

(5) 최종) 'return the copy of the given node as a reference to the cloned graph'라고 하였으므로 the given node(val = 1)로 처음에 만든 clone 바로 return (return clone)

🧑🏻‍💻 0200) 연결요소의 개수 유형

---

1456. Maximum Number of Vowels in a Substring of Given Length / 0033. Search in Rotated Sorted Array

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans=0
        for letter in s[:k]:
            if letter in 'aeiou':
                ans+=1
        start=0
        prev=ans
        for letter in s[k:]:
            if s[start] in 'aeiou':
                prev-=1
            if letter in 'aeiou':
                prev+=1
            ans=max(ans,prev)
            start+=1
        return ans

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start,end=0,len(nums)-1
        while start<=end:
            mid = (start+end)//2
            if target == nums[mid]:
                return mid
            
            #left
            if nums[start] <= nums[mid]:
                if target > nums[mid] or target < nums[start]:
                    start = mid + 1
                else:
                    end = mid - 1
            
            #right
            else:
                if target < nums[mid] or target > nums[end]:
                    end = mid - 1
                else:
                    start = mid + 1
        return -1

 

🧑🏻‍💻 1456) 슬라이딩 윈도우 문제. 정해진 길이만큼 오른쪽 끝까지 슬라이드 진행하면서 맨 앞과 맨 뒤의 글자가 vowel에 들어가는 지에 따라 -=1, +=1. max() 함수 사용해서 업데이트

 

🧑🏻‍💻 0033) 이분탐색 응용버전. 원래 이분탐색은 sorted 된 상태에서 진행하는 것이 국룰이나, rotated sorted array에서 이분탐색을 진행한다는 점이 주목할 만한 부분. 단 rotated sorted array는 sorted된 array 2개가 결합한 것임을 알아야 한다.

: mid 원소가 왼쪽 sorted array에 속하는 지, 오른쪽 sorted array에 속하는 지에 따라서 다르게 경우의 수를 만들어 start, end update

---

0139. Word Break / 0207. Course Schedule

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [True] + [False]* len(s)
        for i in range(1, len(s) + 1):
            for word in wordDict:
                if s[i - len(word): i] == word:
                    dp[i] = dp[i-len(word)]
                if dp[i]: #found True only once
                    break
        return dp[-1]

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        from collections import deque
        indegree = [0] * (numCourses)
        graph = [[] for _ in range(numCourses)]

        for prerequisite in prerequisites:
            x,y=prerequisite[0],prerequisite[1]
            graph[y].append(x)
            indegree[x]+=1
        
        res = 0
        q = deque()

        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)  

        while q:
            node = q.popleft()
            res += 1
            for i in graph[node]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    q.append(i)
                    
        return res==numCourses

 

🧑🏻‍💻 0139) 'leetcode'라는 문자열을 예로 들자면, wordDict = ['leet', 'code']라고 했을 때, DP[x]란 index x까지의 문자열이 wordDict로 만들 수 있는 지의 여부를 뜻한다. 따라서 wordDict를 직접 돌며 word의 길이를 w라고 한다면 DP[x] = DP[x-w]라고 할 수 있다. 아래 그림 참조.

🧑🏻‍💻 0207) prerequisite으로 course의 순서가 정해진 상태에서, 모든 course를 들을 수 있는 지, 즉 모든 노드를 traverse할 수 있는 지 = 위상 정렬 가능 여부를 묻는 문제. 위상 정렬이 가능한 지 확인하기 위해선, 생성한 그래프가 DAG(Directed Acyclic Graph; 방향 비순환 그래프)를 만족해야 한다. queue를 만들어 popleft()로 꺼낼 때마다 방문 확인. 꺼낸 노드의 개수를 누적해서 구한다. 구한 결과와 전체 노드의 개수를 비교하여 같다면 방향 비순환 그래프이므로 true. 같지 않다면 방향 비순환 그래프가 아니므로 false.

---

0236. Lowest Common Ancestor of a Binary Tree / 0046. Permutations

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root:
            if root == p or root == q:
                return root
            
            l = self.lowestCommonAncestor(root.left, p, q)
            r = self.lowestCommonAncestor(root.right, p, q)

            if l and r:
                return root
            else:
                return l or r

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def track():
            if len(ans) == length:
                ans_collections.append(ans[:])
            else:
                for x in range(length):
                    if len(ans) != 0 and nums[x] in ans:
                        continue
                    else:
                        ans.append(nums[x])
                        track()
                        ans.pop()
        nums.sort()
        ans_collections=[]
        ans=[]
        length = len(nums)
        track()
        return ans_collections

 

🧑🏻‍💻 0236) 재귀함수 활용. p와 q 노드의 LCA를 찾는 문제. 이 때 root 자체가 p 또는 q이면 root가 LCA이므로 return root. 그렇지 않다면 재귀적으로 left / right 각각 파고들어서 확인. l과 r 모두 존재한다면(즉, p와 q 각각이 l과 r 또는, r과 l에 존재한다면) 결국은 root가 LCA. 그게 아니라면 l 또는 r 한쪽에 p와 q 두 개가 같이 존재한다면 l 또는 r을 리턴

 

🧑🏻‍💻0046) 전형적인 backtracking 문제. 먼저 sorting하고 진행. 이 때, 적절한 ans를 찾을 때마다 ans_collections list에 ans를 append한다. ans_collections.append(ans)를 한다면, ans의 reference를 append하므로, 실제 ans 자체의 current copy를 가져오는 것이 아님. 따라서 이후 ans가 계속 변할 때마다 ans의 내용도 변한다. 따라서 ans_collections.append(ans[:]) 코드(shallow copy of ans)를 사용해 append를 해야 한다.

---

0056. Merge Intervals / 0011. Container with Most Water

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ans=[]
        intervals.sort(key=lambda x: x[0])
        for start,end in intervals:
            if not ans:
                ans.append([start,end])
            elif ans[-1][1] < start:
                ans.append([start,end])
            else: #if overlapped
                ans[-1][1] = max(ans[-1][1], end)
        return ans

class Solution:
    def maxArea(self, height: List[int]) -> int:
        res = 0
        l,r = 0,len(height)-1

        while l < r:
            area = (r-l) * min(height[l], height[r])
            res = max(res, area)

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return res

 

🧑🏻‍💻 0056) 먼저 첫번째 요소를 오름차순 기준으로 정렬한 뒤, intervals list 직접 for문으로 돌리면서 마지막 ans[-1][1]와 start 비교. 바꿔야 하면 ans[-1][1] 자체를 바꿈

 

🧑🏻‍💻 0011) 투 포인터 O(N)으로 풀어야 TLE 되지 않는다. 맨 왼쪽과 오른쪽에 포인터를 두고 당장의 두 막대 중 최솟값을 가리키는 막대를 중간 방향으로 이동. 최댓값을 가리키는 막대를 이동하면 최솟값을 가리키는 막대보다 같거나 작은 막대만 실제 면적 계산에 적용되므로 최솟값을 가리키는 막대를 이동하는 데 초점을 두어야 한다. 그렇다면 O(N) 시간 복잡도로 이동해서 optimal solution을 찾는 것이 보장되어 있을까? 증명해보자.

 

★ optimal solution을 가지는 answer 두 막대가 각각 i와 j에 있다고 가정.

: 당장 두 포인터 중 더 작은 포인터를 움직이는게 optimal 보장임을 증명해야 한다. i와 j가 일단 optimal이라 가정. 그렇다면 i의 왼쪽 막대들과 j의 오른쪽 막대들은 무조건 min(i,j)보다 작거나 같다. 왜냐하면 반대로 크다면 더 큰 너비에 높이는 i 또는 j를 가지기 때문. 따라서 맨 처음 i를 맨 왼쪽, j를 맨 오른쪽에 두고 시작하는 건, i의 왼쪽과 j의 오른쪽(당연히 두 곳 다 blank)이 모두 min(i,j)보다 작기 때문이고, 현 상황에서 optimal한 상태. 그 상태에서 계속 greedy하게 optimal한 상태를 찾아 나가며 two pointers중 min(i,j)를 중앙쪽으로 이동하며 optimal solution update한다고 생각하면 된다!

---

0019. Letter Combinations of a Phone Number / 0416. Partition Equal Subset Sum

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        digitToChar = {"2" : "abc", "3" : "def", "4" : "ghi", "5" : "jkl",
        "6" : "mno", "7" : "qprs", "8" : "tuv", "9" : "wxyz"}

        def track(i, curStr):
            if len(curStr) == len(digits):
                res.append(curStr)
                return
            for c in digitToChar[digits[i]]:
                track(i+1, curStr+c)
        
        if digits:
            track(0, "")
        
        return res

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2: return False
        dp = set()
        dp.add(0)
        target = total // 2

        for i in range(len(nums)):
            nextDP = set()
            for t in dp:
                nextDP.add(t + nums[i])
                nextDP.add(t)
            dp = nextDP
        return True if target in dp else False

 

🧑🏻‍💻 0017) 기본 backtracking 문제. index를 활용해 움직이면 좀 더 백트래킹 알고리즘 코드를 간단하게 짤 수 있다.

 

🧑🏻‍💻 0416) for문을 직접 돌리면서 예를 들어 [1, 2, 3, 4]라면 [1,2]까지의 list에서 만들 수 있는 모든 subset에서 그 다음 원소 3을 더했을 때에 만들어질 수 있는 모든 subset sum을 다시 update 하며 일일이 DP set update

---