[프로그래머스] 여행 경로(Python)

https://programmers.co.kr/learn/courses/30/lessons/43164?language=python3 

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

처음 문제를 풀 때는 알파벳 정렬만 따져서 풀어서 일부 문제가 안 풀렸다.

내가 틀리는 유형의 테스트 케이스는 하단과 같다.

tickets = [["ICN", "AOO"], ["AOO", "BOO"], ["AOO", "COO"], ["COO", "AOO"], ["BOO", "ZOO"]]

answer = ['ICN', 'AOO', 'COO', 'AOO', 'BOO', 'ZOO']

알파벳 정렬만 따졌기 때문에

ICN - AOO - BOO - ZOO로 모든 경로를 다 따지지 않았다.

 

따라서 하단 코드와 같이 dictonary를 선언해서 갈 수 있는 경로를 미리 설정하고 

경로를 다 훑어봤는지 체크한 후에 answer에 넣기로 했다.

알파벳 정렬은 tickets을 정렬한 후에 추가해서 문제를 해결했다.

 

나의 풀이

def solution(tickets):
    tickets.sort(reverse=True)
    routes = dict()
    for t1, t2 in tickets:
        if t1 in routes:
            routes[t1].append(t2)
        else:
            routes[t1] = [t2]
    stack = ['ICN']
    answer = []
    while stack:
        top = stack[-1]
        if top not in routes or len(routes[top])==0:
            answer.append(stack.pop())
        else:
            stack.append(routes[top].pop())
    return answer[::-1]

 

다른 풀이

from collections import defaultdict
def solution(tickets):
    r = defaultdict(list)
    for i,j in tickets:
        r[i].append(j)
    for i in r.keys():
        r[i].sort()

    s = ["ICN"]
    p = []
    while s:
        q = s[-1]
        if r[q] != []:
            s.append(r[q].pop(0))
        else:
            p.append(s.pop())
    return p[::-1]

defaultdict를 선언해서 dict 초기화 할때도 편하고, 조건 판별할 때도 편하게 활용할 수 있다.

앞으로 기회가 되면 자주 써봐야겠다.