문제

88/100
30분

의도한 것

["최소 필요 피로도", "소모 피로도"] 가 큰 것부터 정렬 후
k가 최소필요 피로도보다 크고
소모피로도에서 k를 뺐을 때 값이 0보다 크면 탐험할 수 있다 생각하여 코드를 짰다.

function solution(k, dungeons) {
    var answer = 0;
    dungeons.sort((a,b)=>{
        let bb = b[0]-b[1], aa=a[0]-a[1]
        
        if(bb !== aa)
        return bb - aa
        if(b[0]!==a[0])
            return b[0]-a[0]})

    dungeons.forEach(arr=>{
        if(arr[0] <= k && k-arr[1] >=0 ){
            k=k-arr[1]
            answer++;
        }

    })
    return answer;
}

몇가지 부분에서 실패를 했다. (아직도 예외케이스는 모르겠다.)

다른사람의 풀이

거의 dfs같은 탐색을 이용한 것 같다

function solution(k, d) {
   const N = d.length
    const visited = new Array(N).fill(0)
    let ans = 0

    function dfs(k, cnt){
        ans = Math.max(cnt, ans)

        for (let j = 0; j < N; j++){
            if (k >= d[j][0] && !visited[j]){
                visited[j] = 1
                dfs(k - d[j][1], cnt + 1)
                visited[j] = 0
            }
        }
    }

    dfs(k, 0)

    return ans;
}

dfs라는 함수를 만들고 내부에서는
for문으로 각각의 배열 값부터 시작을 한다.
(배열의 길이만큼)

• 조건으로 k가 최소필요 피로도보다 크고를 적용했고 방문하지 않은 곳이라면 방문하는 것을 적용한 뒤
  새로운 dfs로 줄어든 k값을 가지고 적용한다.
  이때 cnt는 성공이므로 1개 더해서 새로운dfs의 매개변수로 간다
• 크게 for문 한 사이클이 끝나면 다시 시작해야하므로
  visited는 다시 전부 0으로 맞춰주어 처음부터 시작 되게 해야한다.

예시

30, [[10, 10], [10, 10], [10, 10]]의 매개변수를 받을경우
3의 기댓값을 받는데

function solution(k, d) {
   const N = d.length
    const visited = new Array(N).fill(0)
    let ans = 0

    function dfs(k, cnt){
        ans = Math.max(cnt, ans)

        for (let j = 0; j < N; j++){
            if (k >= d[j][0] && !visited[j]){
                
                visited[j] = 1
console.log(visited)
                dfs(k - d[j][1], cnt + 1)
                visited[j] = 0
            }
        }
    }

    dfs(k, 0)

    return ans;
}

이렇게 console.log를 하면

[ 1, 0, 0 ]
[ 1, 1, 0 ]
[ 1, 1, 1 ]
[ 1, 0, 1 ]
[ 1, 1, 1 ]

[ 0, 1, 0 ]
[ 1, 1, 0 ]
[ 1, 1, 1 ]
[ 0, 1, 1 ]
[ 1, 1, 1 ]

[ 0, 0, 1 ]
[ 1, 0, 1 ]
[ 1, 1, 1 ]
[ 0, 1, 1 ]
[ 1, 1, 1 ]

이렇게 나오고 구분해보면 이와같이 구분하는데
1은 방문한것을 기준으로 하므로
첫번째 배열을 먼저 방문하는 것과
두번째 배열을 먼저 방문하는 것과
세번째 배열을 먼저 방문하는 것으로 나뉜다.

다른 팀원의 풀이

const getPermutations= function (target, num) {
    const results = [];

    if (num === 1) {
        return target.map((value) => [value]);
    }

    target.forEach((fixed, index, origin) => {
      const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
      const permutations = getPermutations(rest, num - 1);
      const attached = permutations.map((permutation) => [fixed, ...permutation]);
      results.push(...attached);
    });

    return results;
};

function solution(k, dungeons) {
    let maxVisitedDungeons = 0;
    const permutations = getPermutations(dungeons, dungeons.length);

    for (const permutation of permutations) {
        let currentTired = k;
        let visitedDungeons = 0;

        for (const [neededTired, useTired] of permutation) {
            // neededTired는 useTired보다는 무조건 크니까 
            // currentTired와 useTired를 비교할 필요는 없지
            // currentTired > neededTired > useTired
            if (currentTired < neededTired) {
                continue;
            }

            currentTired -= useTired
            visitedDungeons += 1

        }
        maxVisitedDungeons = Math.max(visitedDungeons, maxVisitedDungeons)
    }

    return maxVisitedDungeons;
}

가독성이 확실히 좋았다.
가능한 순열 배열을 모두 찾고
해당 for문을 통해 진행을 하였다