출처 : 파이썬 알고리즘 인터뷰

오늘은 어제의 자신감으로 특별히 두 문제를 풀어보았다.

오늘의 문제 1

leetcode 78.Subsets

딱 봐도, 부분집합 구하는 문제이다.

개념도 간단하고 사실 풀고나서 보면 답도 간단한데, 못 풀었다.

생각의 흐름

1. 빈 것을 포함해서 하나씩 요소를 추가할 때마다 result에 append해야겠군
2. 순서나 중복이 허용되지 않으니 index값을 넘겨주어야겠어
3. 종료 조건이 뭐가 있을까? -> 개수를 비교하거나, index를 비교하거나 할 필요가 없는 문제라서 함수가 끝나면 자연스레 종료되어도 상관없음

접근 1

요소 추가할 때마다 result에 append하는 로직

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

최종 코드

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

오늘의 문제 2

leetcode 332.ReconstructItinerary

이 문제는 약간의 해설 도움을 받았으나, 기억을 되살려 그래도 어찌저찌 비벼볼 수 있었던 문제였다.

[출발지, 도착지]의 여정이 적힌 tickets가 주어지고, JFK에서 시작하는 여정을 반환하는 문제.

생각의 흐름

방향이 있네? -> 그래프로 저장해봐야겠다

-> 도착지를 dfs 매개변수로 보내서 출발지로 이용하는 로직 어떤데.

사전배열식의 순서로? -> 문자열 정렬해야겠네

접근 1

그래프로 저장하기

dictionary인데 값을 list로 저장하는 형식의 방향 그래프를 만들어보겠다.

graph = collections.defaultdict(list)

for f, t in tickets:
  graph[f].append(t)
  graph[f].sort(reverse=True) # pop해서 쓸 것이기 때문에 내림차순

접근 2

dfs 작성

def dfs(f):
  while graph[f]:
    dfs(graph[f].pop())
  path.append(f) # dfs가 끝날 때 '출발지'를 append => 거꾸로 저장됨

접근 3

거꾸로 저장되었을테니까 거꾸로 반환

return path[::-1]

최종 코드

class Solution:    
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
      graph = collections.defaultdict(list)
      path = []
      
      for f, t in tickets:
        graph[f].append(t)
        graph[f].sort(reverse=True)
      
      def dfs(f):
        while graph[f]:
          dfs(graph[f].pop())
        path.append(f)
        
      dfs("JFK")
      
      return path[::-1]