[프로그래머스 - Java] 스킬트리

https://programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리

 

풀이

이 문제는 정해진 선행 스킬 순서에 따라 배울 수 있는 스킬 트리의 수를 구하는 문제 입니다.

1. for문을 이용해 하나의 스킬 트리씩 배울 수 있는지를 확인.
2. 각각의 스킬 트리에 대해서 alpha[]라는 배열을 하나 생성하여 해당 스킬트리 문자열에서 그 알파벳(스킬)이 나타는 index를 저장.
3. 이 때 alpha[]는 100로 초기화하여 아예 해당 스킬을 배우지 않는 경우를 처리줌. (선행 스킬을 안배우고 다음걸 배우는 경우가 처리 가능하도록!)
4. 각각의 스킬이 주어진 skill 문자열의 순서대로 배워지는지 확인하기 위해 다음 for문 실행
5. skill 문자열을 순서대로 따라가면서 해당 skill을 배운 idx를 바로 전에 배운 skill의 인덱스와 비교하여 더 현재 skill의 인덱스가 더 작은 경우 불가능한 스킬트리로 판단. 
6. 순서대로 배운 경우 가능한 스킬트리 이므로 answer++

 

Java(자바) 코드

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        int[] alpha = new int[26];
        int temp;
        int bef, after, sw;
        
        for(String data : skill_trees){
            
            //idx를 100으로 초기화
            for(int i=0; i<26; i++)
                alpha[i] = 100;
            
            //스킬트리의 스킬 순서 저장.'A'는 alpha[0]에 저장됨.
            for(int i=0; i<data.length(); i++){
                temp = data.charAt(i)-'A';
                alpha[temp] = i;
            }
            
            temp = skill.charAt(0)-'A';
            bef = alpha[temp];
            sw = 1;
            //배울 수 있는지 확인
            for(int i=1; i<skill.length(); i++){
                temp = skill.charAt(i)-'A';
                after = alpha[temp];
                
                //현재 배우는 skill이 이전에 배운 스킬보다
                //선행되어야하는 경우 -> 불가능
                if(after < bef){
                    sw = 0;
                    break;
                }
                //차례로 배운 경우 비교할 이전 skill의 idx를 현재꺼로 업데이트
                else{
                    bef = after;
                }
                
            }
            //가능한 스킬 트리
            if(sw==1){
                answer++;
            }
                
        }
        return answer;
    }
}