[프로그래머스] LEVEL2 스킬트리 JAVA

스킬트리

문제링크

풀이

구현
1. skillOrder에 해당 값이 몇번째의 스킬 트리인지 표시한다.
알파벳이 26개 이고, 대문자 알파벳이 단 한개씩만 존재한다는 것을 이용하여 skillOrder에 표시하였다.
2. skill_trees을 돌면서 cnt로 현재 몇번째 스킬트리까지 완료했는지 확인한다.
isPossible로는 해당 스킬트리가 가능한지 여부를 확인한다.

• cnt == skill.length() 인 상황, 즉 확인할 스킬트리를 모두 완료한 경우, 이후 스킬을 확인하지 않는다.
• cur == skill.charAt(cnt)로 스킬트리순서에 맞는 경우에만 확인했다라는 표시로 cnt++를 한다.
• skillOrder[cur - 'A'] != 0 && skillOrder[cur - 'A'] > cnt 인 경우는
  skill에 존재하는 스킬인지 확인하고 존재하지만, 선행스킬을 배우지 않은 상태이므로 ìsPossible = false로 설정한다.

3. isPossible 이 true 인 경우에만 answer++하여 최종 answer을 리턴한다.

코드

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        
        int[] skillOrder = new int[26];
        for (int i = 0; i < skill.length(); i++) {
            skillOrder[skill.charAt(i) - 'A'] = i + 1;
        }
        for (int i = 0; i < skill_trees.length; i++) {
            int cnt = 0;
            boolean isPossible = true;
            
            for (int j = 0; j < skill_trees[i].length(); j++) {
                if (cnt == skill.length()) {
                    break;
                }
                
                char cur = skill_trees[i].charAt(j);
                if (cur == skill.charAt(cnt)) {
                    cnt++;
                    continue;
                }
                
                if (skillOrder[cur - 'A'] != 0 && skillOrder[cur - 'A'] > cnt) {
                    isPossible = false;
                    break;
                }
            }
            if (isPossible) {
                answer++;
            }
        }
        return answer;
    }
}