문제
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.
입력
skill : "CBD"
skill_trees : ["BACDE", "CBADF", "AECB", "BDA"]
출력
2
제한 사항
스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
스킬 순서와 스킬트리는 문자열로 표기합니다.
- 예를 들어, C → B → D 라면 "CBD"로 표기합니다.
선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
skill_trees는 길이 1 이상 20 이하인 배열입니다.
skill_trees의 원소는 스킬을 나타내는 문자열입니다.
- skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.
내가 했던 풀이 방법
- skill_trees 배열을 순회할 때마다 order 배열을 선행 스킬 갯수만큼 99로 채워주고 isPossible을 true로 초기화해준다.
- skill을 순회하면서 해당 스킬을 몇 번째로 배우는지를 order에 저장해준다. 즉, 현재 검사하고 있는 스킬트리에서 해당 스킬이 몇 번째 index에 있는지를 저장한다.
- 현재 스킬보다 선행되어야 하는 스킬이 현재 스킬보다 늦게 배울 때 (index 값이 클 때) 스킬트리가 불가능하다. 즉, order[j-1]이 order[j]보다 클 경우 불가능하다. 하지만 만약 order[j]의 값이 -1일 때에는 불가능하다고 확신할 수 없다. 예제 중 선행스킬이 "CBD"이고 스킬트리가 "AECB"일 때, D는 배우지 않으므로 j가 D일 때 order[j]가 -1이게 되고, order[j-1]은 3이다. (index이기 때문) 하지만, D를 배우지 않았을 뿐이지 선행 순서를 어긴 것은 아니므로 불가능하지 않다. 그러므로 order[j-1]가 order[j]보다 크고 order[j]가 -1이 아닐 때 불가능하다. 또 불가능한 경우가 있는데 스킬트리가 "BDA" 일 경우, order[0](=C)은 -1이게 되고, order[1](=B)는 0이게 된다. -1보다 0이 더 크므로, 가능하다고 판단할 수 있지만, C를 선행하지 않았기 때문에 B를 배울 수가 없다. 그러므로 order[j-1]가 -1이지만 order[j]이 -1이 아닐 때에도 불가능하다.
- 불가능한 경우 isPossible을 false로 바꿔주고, 반복문을 탈출한다.
- 스킬트리를 모두 검사했을 때 isPossible이 true인 경우에만 answer를 1 증가시켜준다.
코드
function solution(skill, skill_trees) {
var answer = 0;
let order = Array.from({length: skill.length}, ()=>99);
let isPossible = true;
for(let i=0; i<skill_trees.length; i++) {
order.fill(99);
isPossible = true;
for(let j=0; j<skill.length; j++) {
order[j] = skill_trees[i].indexOf(skill.charAt(j));
if(j!==0 && order[j-1]>order[j]) {
if(order[j]!==-1) {
isPossible = false;
break;
}
} else {
if(order[j]!==-1 && order[j-1]===-1) {
isPossible = false;
break;
}
}
}
if(isPossible) answer++;
}
return answer;
}회고
은근 챙겨줘야 하는 조건들이 있어서 까다롭긴 하지만 예제에서 안 되는 경우를 잘 알려줬기 때문에 놓치지 않고 풀 수 있었다.
Frontend🍓