스킬트리

2026.06.22

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

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

제한 조건

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

입출력 예

문제 풀이

나의 코드

소요 시간: 29분

시간 복잡도: $O(n)$

---

HashSet을 이용하여 해당 스킬이 순서가 필요한 스킬인지 판별

판별 후 현재 찍을 수 있는 상태인지 다시 판별하고 가능하면 넘어가고,
불가능하다면 반복문 중지

---

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int count = 0;
        Set<Character> set = new HashSet<>();
        char skill_order[] = new char[skill.length()];
        
        for (int i = 0; i < skill.length(); i++) {
            set.add(skill.charAt(i));
        }
        
        for (int i = 0; i < skill_trees.length; i++) {
            int index = 0;
            boolean isPossible = true;
            for (int j = 0; j < skill_trees[i].length(); j++) {
                char c = skill_trees[i].charAt(j);
                if (set.contains(c)) { // 스킬 트리에 존재하는 스킬인 경우
                    if (skill.charAt(index) == c) { // 현재 배우는 것이 가능할 때
                        index++;
                    }
                    else { // 현재 배우는 것이 불가능할 
                        isPossible = false;
                        break;
                    }
                }
            }
            if (isPossible) {
                count++;
            }
        }
        return count;
    }
}

AI 코드

시간 복잡도: $O(n)$

---

HashSet을 사용하지 않고,

해당 값이 존재한다면 해당 인덱스를, 존재하지 않는다면 -1을
리턴하는 문자열에서 특정 문자의 인덱스를 반환하는 메서드인
indexOf()를 사용함

---

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int count = 0;
        
        for (String tree : skill_trees) {
            int index = 0;
            boolean isPossible = true;
            for (char c : tree.toCharArray()) {
                if (skill.indexOf(c) != -1) {
                    if (skill.charAt(index) == c) {
                        index++;
                    } else {
                        isPossible = false;
                        break;
                    }
                }
            }
            if (isPossible) count++;
        }
        return count;
    }
}