항해99 2주차 - 일정재구성
Today I learned
2022/01/20
회고록
1/20
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
12장 그래프
1. 이론
2. 문제
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.
Example 1:
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Example 2:
Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.
Constraints:
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi and toi consist of uppercase English letters.
fromi != toi
https://leetcode.com/problems/reconstruct-itinerary/
3. MySol
- Recursive DFS
import collections
def solution(schedules):
arranged = collections.defaultdict(list)
for a,b in sorted(schedules):
arranged[a].append(b)
curr_node = []
next_node = []
result = []
def connection(dep):
while arranged[dep]:
connection(arranged[dep].pop(0))
result.append(dep)
connection('JFK')
return result[::-1]
if __name__ == '__main__':
schedules = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
#[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
#[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
result = solution(schedules)
print('result : ' + str(result))
4. 배운 점
- 해당 문제는 이해하게 되면 DFS및 재귀함수에 대해 이해하는데 굉장히 큰 도움이 되는 문제이다.
5. 총평
재귀, DFS 훈련
Author And Source
이 문제에 관하여(항해99 2주차 - 일정재구성), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsw4215/항해99-2주차-일정재구성저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)