[알고리즘] Summer/Winter Coding(~2018) - [JavaScript] 스킬트리

https://school.programmers.co.kr/learn/courses/30/lessons/49993

프로그래머스

본 포스팅에서 다루는 문제는 위 프로그래머스 링크를 통하여 문제 확인 및 풀이가 가능합니다!

 

1. 문제

1.1. 문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

 

1.2. 제한 조건

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

 

1.3. 입출력 예

skill	skill_trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

• "BACDE": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• "CBADF": 가능한 스킬트리입니다.
• "AECB": 가능한 스킬트리입니다.
• "BDA": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

 

2. 문제 풀이

 

 입력으로 주어진 배열 skill_trees의 원소, 각 스킬 트리가 선행 스킬 순서대로 구성되어 있는 지를 판단하면 되는 문제입니다.

 

해당 문제는 효율성 테스트 없이 정확성 테스트만 있어 중첩 반복문으로 문제 풀이가 가능하지만 효율 및 가독성을 위하여 Map을 사용하였습니다.

 

저는 해당 문제를 아래와 같은 순서로 풀이하였습니다.

 

1.  입력으로 주어진 '선행 스킬 순서'인 skill을 바탕으로 Map을 구성합니다.
   
   입출력 예시였던 "CBD"를 예시로 순서대로 각 문자를 key로 index를 value로 지정하였습니다.
   
   ex) {key: "C", value: 0}, {key: "B", value: 1}, {key: "D", value: 2}
   
   
2. 스킬트리가 선행 스킬 순서를 만족하는지 확인하기 위한 변수 index를 선언하고 0으로 초기화합니다.
   
   CASE 1 - "BACDE"
   - 현재 index는 0인 상황입니다.
   - map에서 "B"를 key로 탐색을 진행한 결과 1이 반환됩니다.
   - index보다 크므로 선행 스킬 순서를 만족하지 못한 스킬트리입니다. -> 불가능 
   
   CASE 2 - "CBADF"
   - 현재 index는 0인 상황입니다.
   - map에서 "C"를 key로 탐색을 진행한 결과 0이 반환됩니다.
   - index와 같으므로 index를 1 증가시킵니다.
   - map에서 "B"를 key로 탐색을 진행한 결과 1이 반환됩니다.
   - index와 같으므로 index를 1 증가시킵니다.
   - A는 선행 스킬 순서에 포함되지 않아 map에서 탐색을 진행하면 undefined가 반환됩니다 -> pass
   - map에서 "D"를 key로 탐색을 진행한 결과 2이 반환됩니다.
   - index와 같으므로 index를 1 증가시킵니다.
   - F는 선행 스킬 순서에 포함되지 않아 map에서 탐색을 진행하면 undefined가 반환됩니다 -> pass
   - 선행 스킬 순서를 모두 만족한 채로 문자열이 종료되었으므로 가능한 스킬트리입니다. -> answer 증가
   
   CASE 3 - "AECB"
   - 현재 index는 0인 상황입니다.
   - A와 E는 선행 스킬 순서에 포함되지 않아 map에서 탐색을 진행하면 undefined가 반환됩니다 -> pass
   - map에서 "C"를 key로 탐색을 진행한 결과 0이 반환됩니다.
   - index와 같으므로 index를 1 증가시킵니다.
   - map에서 "B"를 key로 탐색을 진행한 결과 1이 반환됩니다.
   - index와 같으므로 index를 1 증가시킵니다.
   - 선행 스킬 순서를 모두 만족한 채로 문자열이 종료되었으므로 가능한 스킬트리입니다. -> answer 증가
   
   CASE 4 - "BDA"
   - 현재 index는 0인 상황입니다.
   - map에서 "B"를 key로 탐색을 진행한 결과 1이 반환됩니다.
   - index보다 크므로 선행 스킬 순서를 만족하지 못한 스킬트리입니다. -> 불가능 

 

 

3. 정답 코드

function solution(skill, skill_trees) {
    let answer = 0;
    let map = new Map();
    
    for (let i = 0; i < skill.length; i++) {
        map.set(skill[i], i);
    }
    
    for (let skill_tree of skill_trees) {
        let index = 0;
        let flag = true;
        
        for (let s of skill_tree){
            let result = map.get(s);
            
            if (result != undefined) {
                if (result > index) {
                    flag = false;
                    break;
                } else {
                    index++;
                }
            }
        }
        
        if (flag) {
            answer++;
        }
    }
    
    
    return answer;
}

 

 

3. 마치며

 반복문을 중첩시키는 것으로도 충분히 풀이가 가능한 문제이지만 보다 적합한 자료구조를 사용하는 것으로 코드의 가독성과 효율성을 가져갈 수 있는 문제였습니다.

 

 또한, 본 문제 풀이에서는 선행 스킬의 순서를 준수하는 지에 대한 여부를 검사하는 것이 핵심 로직이기 때문에 Map에서의 검색의 결과인 value로 각 문자의 등장 순서 index를 둔 것이 포인트입니다.