[TIL_Carrotww] 95 - 23/01/30

📝Carrotww의 코딩 기록장

🧲 python algorithm interview

🔍 Leetcode 78 Subsets - Medium

• 내 풀이

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        def dfs(num_list, index):
            result.append(num_list[:])

            for i in range(index, len(nums)):
                num_list.append(nums[i])
                dfs(num_list, i+1)
                num_list.pop()
        dfs([], 0)

        return result

• 책 풀이

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []

        def dfs(index, path):
            result.append(path)
            for i in range(index, len(nums)):
                dfs(i+1, path + [nums[i]])
        dfs(0, [])
        return result

기본만 알면 풀 수 있는 문제다.

🔍 Leetcode 332 Reconstruct Itinerary - Hard

• 처음 풀이

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        result = []
        visited = [0 for _ in range(len(tickets))]
        tickets.sort()

        def dfs(path, visit):
            if len(path) == len(tickets) + 1:
                result.append(path[:])
            for index, val in enumerate(tickets):
                if val[0] == path[-1] and visit[index] == 0:
                    path.append(val[1])
                    visit[index] = 1
                    dfs(path, visit[:])
                    path.pop()
                    visit[index] = 0
        dfs(["JFK"], visited)
        result.sort()

        return result[0]

처음 풀었던 풀이인데 시간초과 난 풀이이다.
visited를 만들어 목적지까지의 모든 경우를 만들고 사전순으로 정렬한 후
가장 앞에있는 값을 반환한다.
하지만

• 책 stack 풀이

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        from collections import defaultdict
        graph = defaultdict(list)
        tickets.sort(reverse=True)
        for a, b in tickets:
            graph[a].append(b)

        result = []
        stack = ["JFK"]
        while stack:
            while graph[stack[-1]]:
                stack.append(graph[stack[-1]].pop())
            result.append(stack.pop())
        return result[::-1]

이 문제를 풀면서 가장 고려해야 했던 부분이 사전순으로 정렬 후 나열했을때 다음
행선지가 끊기는 경우였는데

result.append(stack.pop())

막히는 부분에서 빼준다.

• DFS 풀이

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        from collections import defaultdict
        graph = defaultdict(list)
        tickets.sort(key=lambda x:x[1], reverse=True)
        for start, end in tickets:
            graph[start].append(end)

        result = []
        def dfs(start):
            while graph[start]:
                dfs(graph[start].pop())
            result.append(start)
        dfs("JFK")

        return result[::-1]

이해하는데 좀 걸렸지만 막히는 부분의 예제를 그려가며 보면 이해가 된다.
하지만 이 풀이대로 다시 풀 수 있을까 싶다...
많이 더 풀어봐야겠다.

🧲 python algorithm dfs 연습

🔍 Leetcode 112 Path Sum - Easy

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right and targetSum - root.val == 0:
            return True

        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

이건 쉽다 재귀로 풀었다.

🔍 Leetcode 98 Validate Binary Search Tree - Medium

# 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:
        import math
        return self.Recursion(root, -math.inf, math.inf)

    def Recursion(self, node, min, max):
        if not node:
            return True
        if node.val <= min or node.val >= max:
            return False
        return self.Recursion(node.left, min, node.val) and self.Recursion(node.right, node.val, max)

처음에 함수를 하나 만들지 않고 풀려다가 못풀고 힌트를 보고 함수를 하나 더 많들어서 풀었다. 위 문제를 재귀로 풀었어서 이 문제도 똑같이 시도해봤는데 min, max를 계속 넘길 수 없어서 위와같이 풀었다.