스킬트리

C# 사용

programmers.co.kr/learn/courses/30/lessons/49993#fnref1

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

풀이

스킬을 습득하기 위해선 선행 스킬을 먼저 습득하고 다음 스킬을 습득해야 한다. 스킬의 습득순서는 skill 문자열에 담겨져 있고, 유저들이 만든 스킬트리는 skill_tree 배열에 담겨 있다. 

 

유저들이 만든 스킬트리 중에서 skill에 있는 습득순서를 만족시키는 스킬트리의 갯수를 찾아야 한다. skill 문자열에 포함되지 않는 스킬에 대해서는 습득이 자유롭다. 예제를 보면 알 수 있지만 skill에 포함되어 있는 모든 스킬을 습득하지 않아도 된다.

 

주어진 skill이 "CBD"일 경우 C를 먼저 습득하고 B를 습득할 수 있고, B를 습득해야 D를 습득할 수 있다. <키, 밸류> 값을 가지는 자료구조인 해시테이블이나 딕셔너리를 사용해서 키값과 밸류값 비교를 통해 스킬트리의 습득 순서를 비교해볼려고 생각했는데, 배열 역시 인덱스 번호와 원소를 가지고 키 - 밸류 처럼 사용할 수 있다는 사실을 깨달았다.

 

문자열은 문자로 이루어진 배열이므로 배열의 인덱스 번호를 키값으로, 배열의 원소를 밸류값으로 취급해서 사용해도 문제를 해결할 수 있다.

 

string 클래스의 IndexOf 메소드를 사용하면 인덱스 번호를 통해 현재 몇 단계까지 스킬을 습득했는지, skill에 없는 스킬인지(IndexOf 메소드를 실행해서 해당 원소가 문자열에 없으면 -1을 반환함.) 손쉽게 파악할 수 있다.

 

유저가 만든 스킬트리가 습득이 불가능한 스킬트리일 경우는 현재 습득한 스킬의 인덱스 번호보다 비교 대상이 되는 유저가 만든 스킬트리의 스킬 중에 상위 스킬이 먼저 나타날 경우, 다시말해 인덱스 번호가 더 높을 경우이기 때문에 조건문을 통해 판단을 해서 답을 도출하면 된다.

 

using System;

public class Solution {
    public int solution(string skill, string[] skill_trees) {
        int answer = 0;
        int lengthOfSkill_trees = skill_trees.Length;

                for (int i = 0; i < lengthOfSkill_trees; i++)
                {
                    bool isOK = true;
                    string skillTree = skill_trees[i];
                    int indexOfSkill = 0;

                    for (int j = 0; j < skillTree.Length; j++)
                    {

                        if (indexOfSkill == skill.IndexOf(skillTree[j]))
                        {
                            indexOfSkill++;
                        }
                        else if (indexOfSkill > skill.IndexOf(skillTree[j]))
                        {
                            continue;
                        }
                        else if (indexOfSkill < skill.IndexOf(skillTree[j]))
                        {
                            isOK = false;
                            break;
                        }
                    }

                    if (isOK)
                    {
                        answer++;
                    }
                }
        return answer;
    }
}