프로그래머스 - 10

Level 2

---

피로도

문제 링크

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다.

유저의 현재 피로도 k와 각 던전별 “최소 필요 피로도”, “소모 피로도”가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

---

풀이

• DFS 활용

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

  let visited = Array.from(new Array(d.length), () => false);

  function DFS(hp, L) {
    answer = Math.max(answer, L);

    for (let i = 0; i < d.length; i++) {
      if (!visited[i] && d[i][0] <= hp) {
        visited[i] = true;

        DFS(hp - d[i][1], L + 1);

        visited[i] = false;
      }
    }
  }

  DFS(k, 0);

  return answer;
}

---

완전 탐색 - DFS

1. DFS(Depth-First-Search) 란? 루트 노드에서 시작해서 한 분기를 모두 방문하고 다음 분기로 넘어가는 방식입니다.

인접 노드를 깊이 우선으로 탐색하기 때문에 깊이 우선 탐색, DFS 라고 불립니다.

---

[3차] 압축

문제 링크

---

풀이

function solution(msg) {
  var answer = [];
  let charcode = "A".charCodeAt(0);
  let arr = new Array(26)
    .fill(0)
    .map((x, i) => String.fromCharCode(charcode + i));

  let w = "";

  for (let i = 0; i < msg.length; i++) {
    w += msg[i];

    if (!arr.includes(w)) {
      let index = arr.indexOf(w.slice(0, -1));
      answer.push(index + 1);

      arr.push(w);
      w = msg[i];
    }
  }

  if (w) answer.push(arr.indexOf(w) + 1);

  return answer;
}

---

땅따먹기

문제 링크

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다.

단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

---

풀이

• DFS 활용

  시간초과 발생

function solution(land) {
  var answer = 0;

  function DFS(sum, L, idx) {
    if (L == land.length) {
      answer = Math.max(answer, sum);
      return;
    }

    for (let i = 0; i < land[0].length; i++) {
      if (idx !== i) {
        DFS(sum + land[L][i], L + 1, i);
      }
    }
  }

  DFS(0, 0, 0);

  return answer;
}

---

다른 풀이

function solution(land) {
  var answer = land.shift();

  for (let i = 0; i < land.length; i++) {
    let tmp = [];

    for (let j = 0; j < land[0].length; j++) {
      let max = Math.max(...answer.filter((x, i) => i !== j));
      tmp.push(land[i][j] + max);
    }

    answer = tmp;
  }

  return Math.max(...answer);
}

---

게임 맵 최단거리

문제 링크

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요.

단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

---

풀이

function solution(maps) {
  let xLen = maps[0].length;
  let yLen = maps.length;
  let goal = [xLen - 1, yLen - 1];

  let dx = [1, -1, 0, 0];
  let dy = [0, 0, 1, -1];

  let queue = [];
  queue.push([0, 0, 1]);

  while (queue.length) {
    let [curX, curY, move] = queue.shift();

    if (curX == goal[0] && curY == goal[1]) return move;

    for (let i = 0; i < 4; i++) {
      let nx = dx[i] + curX;
      let ny = dy[i] + curY;

      if (nx >= 0 && nx < xLen && ny >= 0 && ny < yLen && maps[ny][nx] === 1) {
        queue.push([nx, ny, move + 1]);
        maps[ny][nx] = 0;
      }
    }
  }

  return -1;
}

---

스킬트리

문제 링크

---

풀이

function solution(skill, s) {
  let answer = 0;

  let arr = skill.split("");

  for (let tree of s) {
    let isCan = true;

    for (let i = 0, j = 0; i < tree.length && j < arr.length; i++) {
      if (!arr.includes(tree[i])) continue;
      if (arr[j++] == tree[i]) continue;

      isCan = false;
    }

    if (isCan) answer++;
  }

  return answer;
}