[프로그래머스] 스킬트리

코딩테스트 연습 - 스킬트리

코딩테스트 연습 - 스킬트리

Summer/Winter Coding(~2018)

LEVEL 2

문제설명

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

• 선행 스킬 순서대로 스킬을 익혀야 한다. 예를 들어 선행 스킬 순서가 A -> B -> C일때, C를 배우려면 B를 먼저 배워야 하고, B를 배우려면 A를 먼저 배워야 한다.

• 스킬은 알파벳 대문자로 표기한다.

• 스킬 순서와 스킬트리는 문자열로 표기한다. 예를 들어 A -> B -> C라면 'ABC'로 표기한다.

• skill의 길이는 1 이상 26 이하이며 스킬은 중복되지 않는다.

INPUT

skill

• 선행 스킬 순서를 담은 문자열

• 알파벳 대문자만으로 이루어져 있으며 각 문자는 하나의 스킬을 나타냄

• 1 ≤ skill의 길이 ≤ 26

skill_trees

• 스킬트리를 나타내는 문자열을 담은 배열

• 1 ≤ skill_trees의 길이 ≤ 20

• 1 ≤ skill_trees의 원소 길이 ≤ 26

OUTPUT

• 가능한 스킬트리 개수 (0 이상의 정수)

나의 풀이

1. 가능한 스킬트리 개수를 담은 변수 answer를 선언한다.

2. skill_trees 배열의 각 스킬트리를 순회한다.

   • 선행 스킬에서 다음으로 익혀야 할 스킬의 인덱스를 담은 변수 nextSkillIdx 선언
   • 현재 탐색 중인 스킬트리가 가능한지 여부를 담은 변수 isPossible 선언
   1. 현재 탐색 중인 스킬트리의 각 스킬(문자)을 순회한다.
      1. 만약 현재 탐색 중인 스킬(문자)이 선행 스킬에서 요구하는 스킬인데 다음으로 익혀야 할 스킬이 아닌 다른 스킬일 경우 isPossible을 false로 바꾸고 반복문을 중지한다.
      2. 만약 현재 탐색 중인 스킬(문자)이 다음으로 익혀야 할 스킬이 맞다면 nextSkillIdx를 1 증가시킨다.
   2. 전체 스킬 탐색이 끝난 후에도 isPossible이 true라면 현재 탐색 중인 스킬트리는 가능한 스킬트리이므로 answer를 1 증가시킨다.

3. answer를 return 한다.

function solution(skill, skill_trees) {
  // 1. 가능한 스킬트리 개수를 담을 변수 answer를 선언한다
  let answer = 0;
  // 2. skill_trees 배열의 각 스킬트리를 순회한다
  for (let tree of skill_trees) {
    let nextSkillIdx = 0; // 선행 스킬에서 다음으로 익혀야 할 스킬의 인덱스
    let isPossible = true; // 현재 탐색 중인 스킬트리가 가능한지 여부
    // 2-1. 현재 탐색 중인 스킬트리의 각 스킬(문자)을 순회한다
    for (let char of tree) {
      const charIdx = skill.indexOf(char);
      // 2-1-1. 만약 현재 탐색 중인 스킬(문자)이 선행 스킬에서 요구하는 스킬인데 다음으로 익혀야 할 스킬이 아닌 다른 스킬일 경우 isPossible을 false로 바꾸고 반복문을 중지한다
      if (charIdx !== -1 && charIdx !== nextSkillIdx) {
        isPossible = false;
        break;
      }
      // 2-1-2. 만약 현재 탐색 중인 스킬(문자)이 다음으로 익혀야 할 스킬이 맞다면 nextSkillIdx를 1 증가시킨다
      if (charIdx === nextSkillIdx) nextSkillIdx++;
    }
    // 2-2. 전체 스킬 탐색이 끝난 후에도 isPossible이 true라면 현재 탐색 중인 스킬트리는 가능한 스킬트리이므로 answer를 1 증가시킨다
    if (isPossible) answer++;
  }
  // 3. answer를 return한다
  return answer;
}