[프로그래머스][Kotlin] 피로도

해당 문제의 경우 저는 dfs를 이용하여 모든 경우의 수를 확인하여 결과 값을 확인하였습니다. 

처음에는 dfs비슷하게 코드를 작성하였었으나, 통과 후 다른 사람들의 코드를 살짝 봤는데  훨씬 간결하게 풀 수 있는 것을 보게 되었습니다. 그리고 제가 작성한 코드와 차이가 나는 이유를 곰곰히 생각해 보니 해당 문제의 태그는 완전탐색으로 되어있는 점과 dungeons의 꽂혀 체력에 관하여 생각을 미처 못했던 이유 였습니다.

그래서 바로 포커스를 바꿔 체력에 맞춰서 작성 하였더니 실행시간이 대폭 감소 하는 것을 확인 할 수 있었습니다.

 

앞으로는 특정자료 및 특정 방법에만 꽂혀서 더욱 원활한 방법을 생각 못하는 것을 주의하며 코드를 작성해야겠다는 생각을 하게 되는 문제였습니다. 

 

하기는 제가 처음 작성한 코드(dungeons 꽂힌 코드)와 실행 결과 입니다.

import java.lang.Math.max

class Solution {

    lateinit var visit : BooleanArray
    var answer: Int = -1
    lateinit var dungeon : Array<IntArray>
    fun solution(k: Int, dungeons: Array<IntArray>): Int {
        visit = BooleanArray(dungeons.size){true}
        dungeon = dungeons
        for(i in 0 .. dungeons.size-1){
            var temp = ArrayList<Int>()
            temp.add(i)
            dfs(k,temp,i)
            visit[i] = true
        }

        return answer
    }

    fun dfs(hp:Int, oner:ArrayList<Int>,now:Int){
        visit[now] = false

        var temp1 = ArrayList<Int>()
        for(i in oner){
            temp1.add(i)
        }
        if(temp1.size == dungeon.size){
            var point = hp
            var count = 0
            for(i in 0 .. dungeon.size-1){
                val clear = temp1[i]
                if(point >= dungeon[clear][0]){
                    point -= dungeon[clear][1]
                    count++
                } else {
                    break
                }
            }
            answer = max(answer,count)
            return
        }
        for(i in 0 .. dungeon.size-1){
            if(visit[i]){
                temp1.add(i)
                dfs(hp,temp1,i)
                visit[i] = true
                temp1.removeLast()
            }
        }
    }
}

실행 결과

테스트 1 〉	통과 (5.18ms, 61.8MB)
테스트 2 〉	통과 (5.10ms, 61.3MB)
테스트 3 〉	통과 (6.38ms, 61.9MB)
테스트 4 〉	통과 (5.97ms, 61MB)
테스트 5 〉	통과 (8.68ms, 69.6MB)
테스트 6 〉	통과 (14.94ms, 67.8MB)
테스트 7 〉	통과 (57.30ms, 80.1MB)
테스트 8 〉	통과 (55.90ms, 80.2MB)
테스트 9 〉	통과 (6.28ms, 62MB)
테스트 10 〉	통과 (15.28ms, 67.6MB)
테스트 11 〉	통과 (5.33ms, 60.5MB)
테스트 12 〉	통과 (52.22ms, 79.5MB)
테스트 13 〉	통과 (50.95ms, 79.9MB)
테스트 14 〉	통과 (50.49ms, 79.8MB)
테스트 15 〉	통과 (49.24ms, 80.2MB)
테스트 16 〉	통과 (14.49ms, 69.8MB)
테스트 17 〉	통과 (50.75ms, 78.9MB)
테스트 18 〉	통과 (5.16ms, 62.9MB)
테스트 19 〉	통과 (5.83ms, 61.2MB)

 

하기 코드는 다른 사람들의 코드를 보고 체력에 포커스를 맞춰 작성한 코드 및 실행 결과 입니다.

import java.lang.Math.max

class Solution {

    lateinit var visit : BooleanArray
    var answer: Int = -1
    lateinit var dungeon : Array<IntArray>
    fun solution(k: Int, dungeons: Array<IntArray>): Int {
        visit = BooleanArray(dungeons.size){true}
        dungeon = dungeons
        for(i in 0 .. dungeons.size-1){
            if(visit[i] && k-dungeon[i][0] >= 0){
                dfs(k-dungeon[i][1],i,1)
            }
            visit[i] = true
        }

        return answer
    }

    fun dfs(hp:Int,now:Int,count:Int){
        visit[now] = false
        answer = max(answer,count)
        for(i in 0 .. dungeon.size-1){
            if(visit[i] && hp-dungeon[i][0] >= 0){
                dfs(hp-dungeon[i][1],i,count+1)
            }
        }
        visit[now] = true
    }
}

실행 결과

테스트 1 〉	통과 (0.06ms, 61.2MB)
테스트 2 〉	통과 (0.06ms, 61.4MB)
테스트 3 〉	통과 (0.05ms, 62.5MB)
테스트 4 〉	통과 (0.33ms, 60.4MB)
테스트 5 〉	통과 (0.73ms, 61.3MB)
테스트 6 〉	통과 (1.77ms, 60MB)
테스트 7 〉	통과 (3.40ms, 60MB)
테스트 8 〉	통과 (4.85ms, 60.7MB)
테스트 9 〉	통과 (0.05ms, 61.8MB)
테스트 10 〉	통과 (0.96ms, 61.9MB)
테스트 11 〉	통과 (0.03ms, 62.1MB)
테스트 12 〉	통과 (1.42ms, 62.8MB)
테스트 13 〉	통과 (0.47ms, 61.1MB)
테스트 14 〉	통과 (0.21ms, 60.9MB)
테스트 15 〉	통과 (0.09ms, 61.1MB)
테스트 16 〉	통과 (0.09ms, 61.5MB)
테스트 17 〉	통과 (0.17ms, 60.9MB)
테스트 18 〉	통과 (0.04ms, 60MB)
테스트 19 〉	통과 (0.13ms, 61.4MB)