Portfolio

문제

풀이

은찬


function solution(k, dungeons) {
    let answer = 0;
    const {length} = dungeons;
    const array = [];
    const nums = [];
    
    const dfs = (arr, acc) => {
        if(!arr.length){
            array.push(acc);
            return;
        }
        
        arr.forEach((n, index) => {
            const copy = arr.slice();
            copy.splice(index, 1);
            dfs(copy, acc.concat(n));
        });
    }
    
    for(let i = 0; i < length; i++){
        nums.push(i);
    }
    
    dfs(nums, []);
    
    for(let i = 0; i < array.length; i++){
        let currentK = k;
        let count = 0;
        
        array[i].forEach((val) => {
            if(currentK >= dungeons[val][0]){
                currentK -= dungeons[val][1];
                count++;
            }
        });
        
        answer = answer < count ? count : answer;
    }
    
    return answer;
}

재영

리팩토링 전

(worst: 9000ms)


const solution = (k, dungeons) => {
  let maxCount = 0;
  const dungeonsCount = dungeons.length; // 던전 길이
  const queue = []; // 큐 생성

	// 큐 초기화
  for (let i = 0; i < dungeonsCount; i += 1) {
    const [minFatigue, fatigueCost] = dungeons[i];

    if (k >= minFatigue) {
      queue.push([k - fatigueCost, 1, [i]]); // 현재 피로도, 들어간 던전 수, Visited
    }
  }

  while (queue.length) {
    if (maxCount === dungeonsCount) return maxCount; // 더 탐색할 이유 x -> early return

    const [nowFatigue, nowCount, visited] = queue.shift();
    if (visited.length === dungeonsCount) { // 다 방문 시 -> 비교 후 업데이트
      if (maxCount < nowCount) {
        maxCount = nowCount;
      }

      continue;
    }

    for (let i = 0; i < dungeonsCount; i += 1) {
      if (visited.includes(i)) continue;

      const [minFatigue, fatigueCost] = dungeons[i];

      if (nowFatigue >= minFatigue) {
        queue.push([nowFatigue - fatigueCost, nowCount + 1, [...visited, i]]);
      } else {
        queue.push([nowFatigue, nowCount, [...visited, i]]);
      }
    }
  }
  return maxCount;
};

(() => {
  const k = 80;
  const dungeons = [
    [80, 20],
    [50, 40],
    [30, 10],
  ];
  console.log(solution(k, dungeons));
})();

리팩토링

worst: 113ms

큐 클래스 구현

visited를 고정된 길이로 생성

삼항연산자를 이용하여 가독성 높임


class Queue {
  constructor() {
    this.arr = [];
    this.front = 0;
    this.rear = 0;
    this.length = 0;
  }

  push(val) {
    this.arr.push(val);
    this.rear += 1;
    this.length += 1;
  }

  shift() {
    if (this.length) {
      const value = this.arr[this.front];
      delete this.arr[this.front];
      this.front += 1;
      this.length -= 1;
      return value;
    }
  }
}

const solution = (k, dungeons) => {
  let maxCount = 0;
  const dungeonsCount = dungeons.length;
  const queue = new Queue();

  const makeVisited = (count) => new Array(count).fill(false);

  for (let i = 0; i < dungeonsCount; i += 1) {
    const [minFatigue, fatigueCost] = dungeons[i];

    if (k >= minFatigue) {
      const visited = makeVisited(dungeonsCount);
      visited[i] = true;

      queue.push([k - fatigueCost, 1, visited]);
    }
  }

  while (queue.length) {
    if (maxCount === dungeonsCount) return maxCount;

    const [nowFatigue, nowCount, visited] = queue.shift();

    if (visited.every((v) => v)) {
      if (maxCount < nowCount) maxCount = nowCount;
      continue;
    }

    for (let i = 0; i < dungeonsCount; i += 1) {
      if (visited[i]) continue;

      const [minFatigue, fatigueCost] = dungeons[i];
      const nextVisited = visited.map((value, idx) => idx === i || value);

      queue.push(
        nowFatigue >= minFatigue
          ? [nowFatigue - fatigueCost, nowCount + 1, nextVisited]
          : [nowFatigue, nowCount, nextVisited]
      );
    }
  }

  return maxCount;
};

효성


function solution(k, dungeons) {

    const answer = [];
    
    const pushVisitCnt = (arr) => {
        let cnt = 0;
        let rest = k;
        
        arr.forEach(dungeon => {
            const [min, lost] = dungeon;
            
            if(rest >= min) {
                cnt++;
                rest -= lost;
            }
        });
        
    	answer.push(cnt);
    }
    
    const getPermutations = (arr, selectNumber) => {
        const results = [];
        if (selectNumber === 1) {
            return arr.map((value) => [value]);
        }

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

        return results;
    }
    
    const permutatedDungeons = getPermutations(dungeons, dungeons.length);

    permutatedDungeons.forEach(permutatedDungeon => {
        pushVisitCnt(permutatedDungeon);
    });
    
    return Math.max(...answer);
}