프로그래머스_스킬트리_49993

문제 링크

조건

• 선행스킬 조건 적용 : 스파크 -> 라이트닝 볼트 -> 썬더와 같이 배우는 순서가 정해져 있는 스킬들이 있음
• 스킬은 알파벳 대문자로 표기
• skill : 선행 스킬 순서, 길이 1~26
• skill_trees : 스킬을 나타내는 문자열, 길이 2~26

접근 방법

• 26개의 알파벳 길이에 맞게 int 배열을 선언해 주어진 skill 정보로 선행스킬순서를 저장
• 주어진 선행 스킬 순서대로 학습하고 있는지 확인하기 위해 skillCnt 이름의 int 변수 활용

솔루션

class Solution {
    public int solution(String skill, String[] skill_trees) {
       int[] check = new int[26];//선행스킬 순서
        int answer = 0;

        for(int i = 0, len = skill.length(); i < len; i++){
            check[skill.charAt(i) - 'A'] = i+1;//스킬 순서 체크
        }

        for(int i = 0, size = skill_trees.length; i < size; i++){
            String cur = skill_trees[i];
            int skillCnt = 1;
            for(int j = 0, len = cur.length(); j < len; j++){
                int ch = cur.charAt(j) - 'A';
                if(check[ch] == 0) continue;//선행스킬 순서에 해당하지 X스킬
                if(check[ch] == skillCnt){//순서에 맞게 배우고 있다면
                    skillCnt++;
                    continue;
                }else{
                    skillCnt = -1;
                    break;
                }
            }
            if(skillCnt > 0) answer++;
        }

        return answer;
    }
}

리뷰

• 간단한 문제지만 check배열이나 skillCnt와 같은 주요 정보를 저장하는 변수를 선언하여 O(N2) 로직에서 O(N) 로직으로 줄일 수 있었음