[Programmers 코딩테스트 고득점 Kit] 여행경로

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/43164

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

주의: 주어진 tickets 벡터 내 같은 항공권이 여러개 들어갈 수 있습니다.

 

알고리즘은 아래와 같습니다.

1. 주어진 조건 중에 '만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.' 조건이 있으므로 우선 tickets 벡터를 전처리하여 출발지를 key로 갖고 오름차순으로 정렬된 도착지를 value로 갖는 map을 생성해줍니다.

2. 무조건 오름차순 정렬을 기준으로 비행기를 탈 경우 '주어진 항공권은 모두 사용해야 합니다.' 조건을 만족할 수 없는 경우가 있습니다. 따라서, 해당문제는 모든 경우의 수를 구해봐야합니다.

3. 완전탐색을 진행하다가 최초로 모든 항공권을 소비한 경우가 최적의 답이므로 해당 벡터를 반환합니다.

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~