728x90
반응형
문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/43164
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이:
def solution(tickets):
answer = []
routes = dict() # 티켓 정보를 저장하는 딕셔너리
for (start, end) in tickets:
if start in routes:
routes[start].append(end)
else:
routes[start] = [end]
for i in routes.keys():
routes[i].sort(reverse=True) # 뽑아야 하니깐 역순
q = ["ICN"]
while q:
Top = q[-1]
if (Top not in routes) or (not routes[Top]): # 더이상 방문할 곳이 없다 마지막 방문지점
answer.append(q.pop())
else:
q.append(routes[Top].pop())
return answer[::-1]
# print(solution([["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]))
print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]))
첫번째 포문으로 출발지 에서 도착지 가는 딕셔너리
두 번째 포문으로 도착지 알파벳 역순으로 >> 이유 나중에 뽑을때 더 빨리 나오니깐
시작 q에 인천
Top에서 시작하는 곳이 없거나 routes[Top]이 비어있지 않은 경우이다.
그러면 q에 append
그 외에 경우는 도착지점 q에 더함
반응형
댓글