003. 스킬 트리

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

1. 사용 언어 : C#
2. 체감 난이도 : 쉬움
3. 활용 : string 관련 함수

<작성한 코드>

public int solution(string skill, string[] skill_trees)
        {
            int answer = 0;
            bool check;
            int char_index; // 비교하고자 하는 단어의 위치

            foreach (string skill_tree in skill_trees)
            {
                check = true;
                for (int i = skill.Length - 1; i > 0; i--) // skill의 마지막부터 비교함
                {
                    char_index = skill_tree.IndexOf(skill.Substring(i, 1));

                    if (char_index != -1) // 비교하고자 하는 단어가 문자열에 있을 경우
                    {
                        // 선행 스킬이 앞에 없을 경우, false
                        if (!skill_tree.Substring(0, char_index + 1).Contains(skill.Substring(i - 1, 1)))
                            check = false;
                    }
                }

                if (check)
                    answer++;
            }

            return answer;
        }

(아니 이거 C#전용 코드블럭이 있었구낭ㅋㅋㅋㅋ)

이번 알고리즘은 아주 만족이다. 내 생각대로 구현이 완벽히 되기도 했고, 다른 사람들의 코드보다 현저히 짧고 보기 좋았다. 아래는 아이디어 노트이다.

 

아이디어 노트 - 스킬트리

첫 번째로 쓴 것은 선행 스킬 앞에 후행 스킬이 있는지 확인하는 법이다. 이는.. 그냥 억지 같아서 정통으로 가기로했다.

그 방법이 두 번째이다. 마지막 후행 스킬부터 차례대로 검사하여, 앞에 선행스킬을 배웠는지 검사한다.

 

 

 

 

 

 

 

false가 되면 for문 효율을 높히기 위해 바로 break하였다.

역시 쓰면서 하니까 잘 되는 것 같다.

 

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