스킬트리

2026.09.09

문제 풀이

나의 코드

---

소요 시간: 21분
시간 복잡도: $O(N˙L)$
N = skill_trees.length
L = 스킬트리 하나의 최대 길이

---

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

class Solution {
    public int solution(String skill, String[] skill_trees) {
        Set<Character> set = new HashSet<>(); 
        char[] order = new char[skill.length()];
        int idx = 0;
        int cnt = 0;
        boolean isPossible = true;
        
        for (int i = 0; i < skill.length(); i++) { // 스킬트리가 존재하는 스킬을 저장
            char s = skill.charAt(i);
            set.add(s);
            order[i] = s; 
        }
        
        for (int i = 0; i < skill_trees.length; i++) {
            idx = 0;
            isPossible = true;
            for (int j = 0; j < skill_trees[i].length(); j++) {
                char s = skill_trees[i].charAt(j);
                if (set.contains(s)) { // 현재 배우려는 스킬이 선행 스킬을 요구할 때
                    if (order[idx] == s) { // 현재 배울 수 있는 스킬일 때
                        idx++;
                    }
                    else {
                        isPossible = false;
                        break;
                    }
                }
            }
            if (isPossible) {
                cnt++;
            }
        }
        
        return cnt;
    }
}

AI 코드

---

시간 복잡도: $O(N˙L)$

---

코드 분석

전체적인 구조는 동일하나 구현 방식 차이만 존재

---

import java.util.Arrays;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int[] pos = new int[26];               // 알파벳 → skill에서의 순서
        Arrays.fill(pos, -1);                  // -1 = 선행 스킬이 아님
        for (int i = 0; i < skill.length(); i++) pos[skill.charAt(i) - 'A'] = i;

        int answer = 0;
        for (String tree : skill_trees) {
            int idx = 0;                       // 다음에 배워야 할 선행 스킬 순번
            boolean possible = true;

            for (int i = 0; i < tree.length(); i++) {
                int p = pos[tree.charAt(i) - 'A'];
                if (p == -1) continue;         // 선행 스킬과 무관 → 그냥 통과
                if (p != idx) { possible = false; break; }   // 순서 어김
                idx++;
            }
            if (possible) answer++;
        }
        return answer;
    }
}

문제 풀이 후기

문제를 푸는 과정에서 최대한 배열을 사용해서 해결해보려고 했으나,
배열만으로는 부족하다고 판단해서 HashSet을 사용해서 해결했다.

AI 코드를 보며 배열만으로 해결한 것을 보고 아직 한참 멀었다는 생각이 들었다.