ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [프로그래머스][Kotlin] 여행 경로
    프로그래머스 2023. 3. 15. 14:00
    728x90

    해당 문제는 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)

     

Designed by Tistory.