-
[프로그래머스][Kotlin] 여행 경로프로그래머스 2023. 3. 15. 14:00728x90
해당 문제는 dfs 와 map을 적절히 사용하여 풀 수 있습니다.
저의 경우 처음 코드 작성 시 도시 별 방문 할 수 있는 수를 map에 저장하여 작성하였었으나, 중복 티켓이 있을 경우 티켓의 수와 도시 별 방문 할 수 있는 수 이런 정보가 맞지 않아 테스트케이스 1번을 통과 하지 못하였었습니다.
그러다가 해당 문제의 힌트를 보고 티켓을 기준으로 map에 저장하여 체크를 한다면 정상적으로 모든 티켓을 사용하고 모든 도시를 방문하는 경우를 알 수 있겠구나 싶어 코드를 작성하였습니다.
그리고 해당 문제에 대한 코드를 작성하면서 문제에 따라 조금씩은 상이 하겠지만 data class를 이용하여 데이터의 정규화를 해놓고 비교하는 것이 추후 코드 디버깅을 할 때 문제를 조금 더 빨리 찾고 수정 할 수 있겠구나 라고 생각을 하였습니다.
하기는 제가 작성한 코드와 실행 결과 입니다.
class Solution { lateinit var visitcount : HashMap<Info,Int> // 해당 지점에 갈 수 있는 횟수 lateinit var visitList : HashMap<String,ArrayList<String>> // 출발지점에서 갈 수 있는 도시 var possibly = mutableListOf<Array<String>>() var count = 0 data class Info( val start: String, val next: String ) fun solution(tickets: Array<Array<String>>): Array<String> { visitcount = HashMap<Info,Int>() // 해당 지점에 갈 수 있는 횟수 visitList = HashMap<String,ArrayList<String>>() for(ticket in tickets){ if(visitcount.containsKey(Info(ticket[0],ticket[1]))){ visitcount[Info(ticket[0],ticket[1])] = visitcount[Info(ticket[0],ticket[1])]!!+1 } else { visitcount[Info(ticket[0],ticket[1])] = 1 } if(visitList.containsKey(ticket[0])){ visitList[ticket[0]]!!.add(ticket[1]) visitList[ticket[0]]!!.distinct() } else { var temp = ArrayList<String>() temp.add(ticket[1]) visitList[ticket[0]] = temp } } var temp = Array<String>(2,{""}) temp[0] = "ICN" for(i in 0 .. visitList["ICN"]!!.size-1){ temp[1] = visitList["ICN"]!![i] dfs(Info("ICN",visitList["ICN"]!![i]), temp) } possibly.sortWith(java.util.Comparator { o1, o2 -> o1.joinToString().compareTo(o2.joinToString()) }) //println(possibly) return possibly.first() } fun dfs(now: Info,his:Array<String>){ visitcount[now] = visitcount[now]!!-1 if(visitcount.values.sum() == 0){ possibly.add(his) visitcount[now] = visitcount[now]!!+1 return } var temp = Array<String>(his.size+1,{""}) if(!visitList[now.next].isNullOrEmpty()){ for(i in 0 .. his.size-1){ temp[i] = his[i] } for(i in 0 .. visitList[now.next]!!.size-1){ if(visitcount[Info(now.next,visitList[now.next]!![i])]!! > 0){ temp[his.size] = visitList[now.next]!![i] dfs(Info(now.next,visitList[now.next]!![i]),temp) } } } visitcount[now] = visitcount[now]!!+1 } }
실행 결과
테스트 1 〉 통과 (1166.05ms, 392MB) 테스트 2 〉 통과 (9.04ms, 60.5MB) 테스트 3 〉 통과 (11.05ms, 62.2MB) 테스트 4 〉 통과 (14.22ms, 61.4MB) '프로그래머스' 카테고리의 다른 글
[프로그래머스][Kotlin] 베스트앨범 (0) 2023.03.21 [프로그래머스][Kotlin] 모음 사전 (0) 2023.03.19 [프로그래머스][Kotlin] 피로도 (0) 2023.03.12 [프로그래머스][Kotlin] 부대복귀 (0) 2023.03.09 [프로그래머스][Kotlin] 무인도 여행 (0) 2023.03.07