kotlin 프로그래머스 lv2 피로도

해당 문제를 풀때, 완전탐색이라고 적혀져있어서 먼저 완전탐색이 뭔지 확인 후 문제를 읽었다.

완전탐색은 말그대로 모든 경우를 탐색하는것이다.

dungeons배열이 [[80,20],[50,40],[30,10]]   이렇게 주어질때

탐색할 수 있는 모든 경우가 예를들어 dungeons 배열의 1->2->3 순서대로 탐색할 수도있지만

1->3->2 순서대로 탐색할 수도있다.

그래서나는 현재 인덱스부터 시작해서 마지막 던전까지 모든 순서를 변경해서 모든 순열을 확인해보도록 했다.

먼저 solution 함수안에서 모든 내용을 다 적어내기보단 함수를 따로 만들었다.

exploreDungeons 함수는 파라미터로  k:피로도 dungeons:소모피로도배열 index: 현재 dungeons배열에서 몇 행인지

를 나타낸다.

exploreDungeons함수는 모든 던전의 순열을 고려하여 탐험할 수 있는 최대 던전 수를 찾는 보조 함수 라고 할 수 있다.

모든 던전을 탐험했을 때, 남은 피로도를 기준으로 탐험 가능한 최대 던전 수를 계산하는 과정은 다음과 같다.

  if (index == dungeons.size) {//현재 순열에서 모든 던전을 탐험했는지 여부 확인
            var remainingFatigue = k
            var count = 0
            for (dungeon in dungeons) {
                if (remainingFatigue >= dungeon[0]) {
                    remainingFatigue -= dungeon[1] // 던전을 탐험한 후 피로도를 감소
                    count++ // 탐험한 던전 수를 증가
                } else {
                    break // 남은 피로도가 부족하면 더 이상의 던전을 탐험하지 않음
                }
            }
            println("최대 탐험 가능 던전 수 (순열 내): $count")
            return count // 현재 순열에서 탐험한 던전 수를 반환
        }

그리고 현재 인덱스 부터 시작하여 마지막 던전까지 모든 던전의 순서를 변경하여 모든 순열을 확인하는 작업을 해야한다.

던전순서가 1->2->3 도 되지만 1->3->2도 있고 ,  3->1->2 .. 여러경우가 있기 때문이다.

 for (i in index until dungeons.size) {
          
            // 현재 던전과 다른 던전의 순서를 변경
            //※also 수신 객체(dungeons[i])를 변경하지 않고도 부가적인 작업을 수행
            dungeons[index] = dungeons[i].also { dungeons[i] = dungeons[index] } // 던전을 교환
            // 재귀적으로 다음 던전을 계속 탐험합니다.
            val dungeonsExplored = exploreDungeons(k, dungeons, index + 1)
            // 현재 순열에서 탐험할 수 있는 최대 던전 수를 계산
            maxDungeonsExplored = maxOf(maxDungeonsExplored, dungeonsExplored)
            // 다시 던전의 순서를 원래대로 되돌림
            dungeons[index] = dungeons[i].also { dungeons[i] = dungeons[index] } // 던전을 다시 교환
        }

 

결과적으로 코드는 아래와 같이 작성했다.