프로그래머스 피로도 자바스크립트

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

문제 풀이를 위해 생각한 것

1. 각 던전을 원소로 순열을 만든 뒤, 순열을 탐색하는 방법으로 답을 도출할 수  있다.
   
   1. 본 문제에서는 던전 입장 순서가 중요하다. 즉 첫 번째 던전을 먼저 방문할 것인지, n번째 던전을 먼저 방문할 것인지에 따라 다른 결과가 도출된다. 한 번 던전에 입장하면 피로도가 차감되기 때문이다.
   2. 이는 순열의 특성과 일치한다.
2. n개의 던전으로 도출할 수 있는 순열을 만든다. -> 하나의 순열은 방문하는 순서대로 나열된 던전들로 볼 수 있다.
   1. 예시로, _dungeons 배열에는 [[던전1], [던전2], [던전3]]이 들어있다.
3. 각 순열을 탐색한다.
   1. 각 순열을 탐색할 때마다 던전 입장 횟수를 초기화하고 탐색을 시작하며, 로컬 변수 k가 최소 필요도보다 크면 던전 입장 횟수++하고, k -= 던전 탈출 후 차감 피로도이다.
   2. 현재 탐색하고 있는 던전의 필요 피로도가 로컬 변수 k보다 높을 때는 탐색을 종료한다.
4. 탐색이 완료되면 max 던전 입장 횟수와 현재 탐색한 던전 입장 횟수를 비교하여 더 큰 값을 max 던전 입장 횟수로 한다.

 

사용한 자료구조 / 알고리즘

순열 / 완전 탐색

 

풀이 코드

const getDungeons = function (arr, numSelect) {
  if (numSelect === 1) return arr.map((el) => [el]);
  const result = [];

  arr.forEach((fixed, idx, origin) => {
    const rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)];
    const dungeons = getDungeons(rest, numSelect - 1);
    const dungeon = dungeons.map((d) => [fixed, ...d]);

    result.push(...dungeon);
  });

  return result;
};

const searchD = function (arr, k) {
  let localK = k;
  let cnt = 0;

  for (let i = 0; i < arr.length; i++) {
    if (arr[i][0] <= localK) {
      // 방문할 수 있는 던전
      localK -= arr[i][1];
      cnt++;
    } else {
      break;
    }
  }
  return cnt;
};

function solution(k, dungeons) {
  let answer = 0;

  const _dungeons = getDungeons(dungeons, dungeons.length);

  for (let i = 0; i < _dungeons.length; i++) {
    const searchCnt = searchD(_dungeons[i], k);
    if (searchCnt > answer) {
      answer = searchCnt;
    }
  }

  return answer;
}

 

시간 복잡도 분석

 

O(N!).

순열을 활용하기에 시간 복잡도는 O(N!)이다.

 

문제에서 중요한 부분

던전 입장 순서가 중요하다는 것과 순열의 특징을 연관지어 떠올릴 수 있어야 했다.