99클럽 코테 스터디
오늘은 면접 갔다오느라 피곤하기도 하고, 문제를 늦게 풀기 시작했는데 챌린저 문제를 greedy하게 풀려는 여러 시도 끝에 시간 소모를 너무 많이해서, 그냥 챌린저 문제 한개만 올리기로 했다. 자세한 설명도 쓸 기력이 없다...
챌린저 문제 여행경로 : https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=python3#
출처 : 프로그래머스
챌린저 문제 : 여행경로
풀이 접근
우선 그리디하게 갈 수 있는 가장 사전순으로 빠른 공항으로만 이동하다가, 막다른 길이 나올 때까지 이동한다. 이 경로를 answer의 뼈대로 삼는다.
이 때, 중간에 놓친 경로들이 있는데, 이 경로들은 모두 뼈대 경로의 특정한 node에서 출발하는 circle(순환)의 형태를 띠게 된다. 그리고 이 circle을 최대한 뼈대 경로의 뒤쪽에 배치해야 함을 알 수 있다. (동일한 circle을 뒤쪽에 삽입할수록 사전순으로 빠르기 때문)
따라서 뼈대 경로를 뒤에서부터 순회하면서, circle을 삽입할 수 있는 곳에 삽입한다. 이 때 주의할 점은, circle 경로를 생성하는 과정 자체도 이 문제를 푸는 과정과 완전히 같은데, 이를 재귀를 이용해서 풀 수 있다는 점이다. circle을 만들 때도 greedy한 move로 뼈대 경로를 만들고, 뒤쪽에서부터 순회하면서 중간에 삽입할 수 있는 circle이 있는지 확인하고, 가능하면 삽입해서 경로를 채운다.
무슨 말인지 알아먹기 어려울 수 있다고 생각되지만... 오늘은 더 자세히 쓸 여력이 없다.
코드(Python3, 통과, 최대 0.03ms, 10.2MB)
프로그래머스는(난이도가 낮은 문제일수록 더 그런 것 같다) 문제에 써 놓은 조건의 크기보다 테스트케이스 크기가 너무너무 작아서 맘에 안 든다. 아니 공항이 1만개면 티켓이 1억개 있을수도 있는건데, 0.03ms짜리 테케만 넣어두는게 말이 되는가? 썩 맘에 안 든다. 당연히 recursiondepth도 안 늘려줘도 그냥 통과된다.
tickets의 정보들을 dictionary의 형태로 다시 정리하고, dictionary의 각 value들에 해당하는 리스트(특정 key(공항)에서 갈 수 있는 공항들의 리스트)는 내림차순 정렬해서 pop으로 사전순으로 가장 빠른 공항을 뽑을 수 있도록 세팅했다.
그리고 첫 while문으로 answer에 뼈대 경로를 만들어두고 시작한다.
circle_check(arr)은 arr의 경로를 뒤에서부터 앞으로 순회하면서, 아직 쓰지 않은 항공권이 있으면(그리고 그 항공권으로 출발해서 돌다 보면 반드시 circle이 형성된다), 그 지점에 circle을 생성해서 끼워 넣는 함수이다. list를 return하는 것보단 그냥 list 자체를 수정해 버리고 아무것도 return하지 않는 식으로 코드를 짰다.
경로의 중간에 새로운 경로를 끼워 넣는 방식은, 그냥 insert 등의 메서드를 쓸 수도 있겠지만, stack 자료구조를 list로 구현하여 써 보았다.
def solution(tickets):
answer = ['ICN']
t_dict = {} # t_dict[공항]은 해당 공항에서 갈 수 있는 공항의 리스트
for start, end in tickets:
if start in t_dict:
t_dict[start].append(end)
else:
t_dict[start] = [end]
if end not in t_dict:
t_dict[end] = []
for airport in t_dict:
t_dict[airport].sort(reverse = True)
while t_dict[answer[-1]]:
answer.append(t_dict[answer[-1]].pop())
def circle_check(arr):
stack = []
insert_idx = []
insert_circle = []
idx = len(arr) - 1
while arr:
if not t_dict[arr[-1]]:
stack.append(arr.pop())
else:
insert_idx.append(len(arr))
new_circle = [t_dict[arr[-1]].pop()]
while t_dict[new_circle[-1]]:
new_circle.append(t_dict[new_circle[-1]].pop())
circle_check(new_circle)
insert_circle.append(new_circle)
now = 0
for i in range(len(insert_idx)):
ii = insert_idx[i]
ic = insert_circle[i]
for j in range(now, ii):
arr.append(stack.pop())
arr += ic
now = ii
while stack:
arr.append(stack.pop())
return
circle_check(answer)
return answer