•
•
문제 설명 : 도시 운행 정보(path)를 제공해준다. 이를 사용하여, 최종적으로 어떤 목적지에 도착이 될지 반환한다.
•
풀이 방법
◦
우선 이 문제는 모든 도시가 연결된 구조는 아니다. 반드시 한 도시는 다음 도시로 가지 않는 경우가 있기 때문에 dict 를 사용하여, 다음 목적지를 value로 저장한 변수를 만들어둔다.
◦
이를 사용하여, 첫 출발 도시부터 다음 도시를 순회한다.
◦
이때 다음 도시에 대한 정보가 없는 도시가 최종 목적지이기 때문에, 이를 반환하면 된다.
•
시간복잡도 :
•
성공 코드
# O(N + N) -> O(N)
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
# 도시 운행 정보를 dict에 저장 -> O(N)
city_route_info = {start: end for start, end in paths}
# 첫 운행 정보를 저장
current_city, next_city = paths[0]
# 다음 목적지가 있다면 계속 반복
# 문제의 조건에서는 다음 목적지가 없는 도시가 반드시 있기 때문에 -> O(N[While문 동작 횟수])
while next_city:
next_city = city_route_info.get(current_city)
if next_city:
current_city = next_city
return current_city
Python
복사