✔️ 문제

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한 조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  예를 들어, C → B → D 라면 CBD로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

😎 소스 코드

function solution(skill, skill_trees) {
  let answer = 0,
    filtered = [];

  // skill에 해당되는 스킬을 찾아서 temp에 넣어줌
  for (let i = 0; i < skill_trees.length; i++) {
    let temp = []; // temp : skill에 해당되는 문자 저장용
    for (let j = 0; j < skill_trees[i].length; j++) {
      for (let k = 0; k < skill.length; k++) {
        if (skill_trees[i][j] === skill[k]) {
          temp.push(skill_trees[i][j]);
        }
      }
    }
    filtered.push(temp);
  }

  console.log(filtered);

  // 추출한 문자열과 skill 체크
  for (let i = 0; i < filtered.length; i++) {
    if (filtered[i].length === 0) { // skill에 해당되는 스킬이 없는 경우
      answer++;
    }
    for (let j = 0; j < filtered[i].length; j++) {
      if (skill[j] !== filtered[i][j]) {
        break;
      }
      if (j === filtered[i].length - 1) { // skill과 filtered 순서가 일치
        answer++;
      }
    }
  }

  console.log(answer);
  return answer;
}

👍 문제를 풀고 나서

skill_trees에서 skill에 해당되는 스킬을 찾아낼 때 3중 for문을 써서 효율이 안 좋을 것 같지만.. 이 방법밖에 생각이 안 나서 어쩔 수 없었다.

문제 접근 방식은 다음과 같다.

1. skill_trees에서 skill에 해당되지 않는 스킬을 지운 뒤 temp에 넣어준다.
2. temp를 변수 filtered에 push해준다.
3. skill_tress 길이만큼 1과 2 반복
4. 그 후 추출된 문자열(filtered)과 skill의 순서를 체크한다.

풀면서 막혔던 부분은 크게 두 군데가 있었는데,

1. 이차원배열로 만들어서 풀어보려 했는데 생각해보니 굳이 그럴 필요가 없었다.
2. 코드를 다 작성한 뒤, 테스트 케이스를 돌려보는 과정에서 skill의 길이가 1인 경우를 생각 못했다. 예를 들면 'C', ['CXF', 'ASF', 'BDF', 'CEFD']와 같은 경우이다.