[프로그래머스][level3] 여행경로 -python

문제링크

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

 

풀이 

• 딕셔너리와 스택 이용해서 풀이.. 다른 블로그 글을 참고했다.

1. 딕셔너리에 출발지를 key, 도착지를 value로 하여 저장한다.

두번째 예시를 사용하여 설명해보겠다.

tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]

아래처럼 저장될 것이다. 

2. 알파벳 순으로 도착해야한다. 딕셔너리는 list로 popleft()가 지원되지 않고, pop()만 가능하다. 따라서 pop()을 사용하기 위해 내림차순으로 value들을 정리한다. 

3. stack에 'ICN'를 넣고 이를 key로 하여 dic에 value가 있으면 value값을 pop()를 사용하여 빼고 stack에 추가한다. 만약 key가 없거나, key에 해당하는 value의 길이가 0 이라면 key값을 stack에서 빼고 answer에 대입한다. 

4. answer에 거꾸로 추가되므로 reverse 해준다. 

from collections import deque

def solution(tickets):
    
    routes = dict()
	
    # 출발지를 Key, 도착지를 value 로 저장 
    for t1, t2 in tickets:

        if t1 in routes:
            routes[t1].append(t2)
        else:
            routes[t1] = [t2]

	# value 내림차순 정렬 
    for k in routes.keys():
      routes[k].sort(reverse = True)

    stack = deque()
    # stack에 출발지 추가 
    stack.append('ICN')
    answer = []

    while stack:
      start = stack[-1]
      # 딕셔너리에 key가 없거나 key의 value가 없다면 
      if start not in routes or  len(routes[start]) == 0:
      # answer에 추가 
        answer.append(stack.pop())
      else :
      # key의 value 하나 빼고 stack에 추가 
        stack.append(routes[start][-1])
        routes[start].pop()

    answer.reverse()

    return answer