[프로그래머스] 피로도 - JS

피로도

❓ 문제설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

🚫 제한조건

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

✔ 입출력 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

💡 풀이

function solution(k, dungeons) {
  // 내 풀이
  let answer = 0
  const func = (dungeons, index, fatigue, count) => {
    if (dungeons.length === 0) {
      answer = answer < count ? count : answer
      return
    }

    const [need, use] = dungeons.splice(index, 1)[0]
    if (k - fatigue >= need) {
      fatigue += use
      count++
    }
  
    dungeons.forEach((_, index, arr) => {
      func(arr, index, fatigue, count)
    })
  }

  dungeons.forEach((_, index, arr) => {
    func(arr, index, 0, 0)
  })
  return answer

  // 다른사람 풀이 참고
  // 던전을 탐험 못하는 경우 제외하고 탐색
  let answer = 0
  const visit = new Array(dungeons.length).fill(false)

  const dfs = (k, count) => {
    answer = Math.max(answer, count)

    for(let i=0; i < visit.length; i++) {
      const [need, use] = dungeons[i]

      if (!visit[i] && k >= need) {
        visit[i] = true
        dfs(k - use, count + 1)
        visit[i] = false
      }
    }
  }

  dfs(k, 0)
  return answer
}

📝 해설

재귀함수를 사용하여 0번째 index의 던전부터 차례로 모든 던전을 탐색하여 가장 많은 방문 횟수를 리턴하는 func 을 만들었다. (dfs)

 

이후 다른 풀이를 보니 나와 차이점이 있었는데 나의 풀이는 중간에 탐색을 못하더라도 이 후 과정을 진행하였는데 다른 풀이에서는 그 과정을 생략하였다. 1,2,3,4 던전이 있고 1번 던전을 탐험하고 이후 과정을 탐색하고 있는 과정일 때 2번이 불가능한 상황을 가정한다면, 나의 풀이는 1 -> 2(카운트 x) -> 3 or 4 -> ... (1) 의 과정을 진행 하고 다시 1 -> 3 -> 2 or 4 -> ... (2) 과정을 진행하는데 (1) 과 (2) 과정이 중복되는 것을 알 수 있다. 결과적으로 중간에 피로도의 제약으로 탐험을 못하는 경우 그 이후 상황을 생략하고 다음 탐색으로 넘어 가더라도 결국 그 이후 상황과 동일한 과정도 탐색을 한다는 것을 알 수 있다.    

📚 참고자료

- https://kimby.tistory.com/48 (Array 메소드)