1 minute read

332. Reconstruct Itinerary

문제 링크

https://leetcode.com/problems/reconstruct-itinerary/description/

문제 설명

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

  • For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

제한 사항

  • 1 <= tickets.length <= 300
  • tickets[i].length == 2
  • fromi.length == 3
  • toi.length == 3
  • fromi and toi consist of uppercase English letters.
  • fromi != toi

입출력 예 #1

  1. Input : tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
  2. Output : [“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]

입출력 예 #2

  1. Input : tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
  2. Output : [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
  3. Explanation : Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”] but it is larger in lexical order.

문제 풀이

  1. dfs 재귀구현을 통한 풀이, 스택을 이용하기 위해 사전 역순으로 정렬 이후 pop() 사용
  2. 반복 구조로 풀이
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        # 그래프 순서대로 구성, 역순으로 구성한 이유는 pop(0) 보다 pop()이 더 속도가 빠르기 때문
        for a, b in sorted(tickets, reverse=True):
            graph[a].append(b)

        route = []
        def dfs(a):
            # 마지막 값을 읽어 어휘 순 방문
            while graph[a]:
                dfs(graph[a].pop())
            route.append(a)

        dfs('JFK')
        # 다시 뒤집어 어휘 순 결과로
        return route[::-1]

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        # 그래프 순서대로 구성
        for a, b in sorted(tickets, reverse=True):
            graph[a].append(b)

        route, stack = [], ['JFK']
        
        while stack:
            # 반복으로 스택을 구성하되 막히는 부분에서 풀어내는 처리
            while graph[stack[-1]]:
                stack.append(graph[stack[-1]].pop())
            route.append(stack.pop())

        # 다시 뒤집어 어휘 순 결과로
        return route[::-1]

Comments

You May Also Enjoy