[문제 풀이] 여행경로

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

 

해결 과정

와 드디어 풀었다 ㅋ 이 문제 12월인가 처음 접했는데 이제는 문제를 외울판임 ㅋ

아무튼, 그 때 당시에는 DFS/BFS 에만 골두하느라, 현재 푼 방식을 생각을 못했던 것일 수도.

2번째 풀이 때는 모범답안을 봤었는데, 아니 어떻게 저렇게 stack을 가지고 풀 수 있나? 싶어서 우선 패스.

근데 이번에 또 만났다. 문제에서 의도한대로 깔끔하게 푼진 모르겠지만, 나름 내 생각의 흐름대로 풀었음.

나의 풀이

def solution(tickets):
    ticketsNum = len(tickets)
    answer = []
    caseStack = []
    stack = []

    startCity = "ICN"
    
    while len(stack) != ticketsNum and tickets:
        tempCase = []
        
        for index, ticket in enumerate(tickets):
          if ticket[0] == startCity:
            tempCase.append((len(stack), ticket))

        if tempCase:
          tempCase.sort()

          nextCase = tempCase.pop(0)
          stack.append(nextCase[1])
          startCity = nextCase[1][1]
          tickets.remove(nextCase[1])

          caseStack += tempCase

        else:
          nextCase = caseStack.pop()

          while len(stack) != nextCase[0]:
            tickets.append(stack.pop())

          stack.append(nextCase[1])
          startCity = nextCase[1][1]
          tickets.remove(nextCase[1])

    answer = [x[0] for x in stack]
    answer.append(stack[-1][1])
    
    return answer

 

다른 풀이

상위에 있는 좋아요 많이 받은 풀이들을 보니, 다음과 같이  tickets를 dictionary로 정리해둔게 많았다.

{'ICN': [], 'AOO': [], 'BOO': [], 'COO': [], 'DOO': [], 'EOO': []}

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]

 

from collections import defaultdict

def solution(tickets):
    routes = defaultdict(list)

    for ticket in tickets:
        routes[ticket[0]].append(ticket[1])
    
    for route in routes:
        routes[route].sort()
    
    stack = ["ICN"]
    reverseRoute = []

    while len(stack) > 0:
        top = stack[-1]

        if top in routes and len(routes[top]) > 0:
            stack.append(routes[top].pop(0))
        else:
            reverseRoute.append(stack.pop())

    return reverseRoute[::-1]

아니 이거 디버깅해보는데, 이해가 안됨. 순서대로 돌다가, 다음 경로가 존재하지 않으면 p라는 곳에 차례대로 저장해두고, 끝에는 s에 있는 것들도 p라는 곳에 차례대로 저장한 뒤에, p의 역순으로 출력한게 정답이라는데 이게 어떻게 성립하는거임?

 

IDEA

list.pop()은 기본적으로 리스트의 제일 마지막 원소를 내뱉는다. 

동일한 함수로 index를 주면, list.pop(index) 그 인덱스의 원소를 내뱉기도 한다.