[Programmers 문제풀이 JAVA] Level 2 스킬 트리

📄 스킬트리

🔗 문제 풀러가기

문제에서 주어진 조건은 생각보다 단순합니다. 먼저 모든 문자열은 알파벳 대문자로만 이루어져 있습니다. 그리고 스킬의 총 길이는 최대 26이며 중복 또한 없습니다. 완전 탐색으로 진행해도 쉽게 문제를 해결할 수 있는 유형입니다.

문제 풀이 접근 방식은 다음과 같이 할 수 있습니다.
스킬트리 안에 스킬 순서에 포함되는 스킬이 있을 시 선행 스킬을 배웠는지 확인합니다. 여기서 문제를 조금 단순화 시킬 수 있는데 현재 스킬을 배우기 위해 이전의 모든 선행 스킬을 다 확인 할 필요가 없습니다. 바로 이전의 선행 스킬만 확인하면 됩니다. 만약 이전의 선행 스킬을 배우지 않았다면 이미 이루어 질 수 없는 조합이기 때문입니다.
여기서 주의해야 할 점은 스킬의 index가 0번째라면 out of index가 발생하기 때문에 예외처리를 해줘야 합니다.

 

\

---

🌱 Solution 함수

public int solution(String skill, String[] skill_trees) {
    int answer = 0;

    for (int i = 0; i < skill_trees.length; i++) {
        if (solve(skill, skill_trees[i])) answer++;
    }

    return answer;
}

🌱 solve 함수

public boolean solve(String skill, String skillTree) {
    boolean[] learned = new boolean[skill.length()];
    int preIndex = -1;

    for (int i = 0; i < skill.length(); i++) {
        char c = skill.charAt(i);
        for (int j = 0; j < skillTree.length(); j++) {
            if (skillTree.charAt(j) == c) {
                // 스킬트리에 선행 순서를 확인해야 할 스킬이 있다면
                // 가능한 순서인지 확인
                if (!isPossible(j, preIndex, i, learned)) return false;
                learned[i] = true;
                preIndex = j;
                break;
            }
        }
    }

    return true;
}

🌱 스킬 트리 순서 확인 함수

/*
* @param curIndex : 스킬 트리에서 현재 확인하는 스킬
* @param preIndex : 스킬 트리에서 이전에 확인한 스킬
* @param skillIndex : 스킬 순서에서 현재 확인하는 스킬
* @param learend : 선행 스킬 배움의 유무
*/
public boolean isPossible(int curIndex, int preIndex, int skillIndex, boolean[] learned) {
    if (curIndex < preIndex) return false;
    if (skillIndex > 0 && !learned[skillIndex - 1]) return false;
    return true;
}