[Programmers] 스킬트리

단순 구현으로 접근하였다.

우선 알파벳의 순위를 정해주는 order 배열을 통해 우선순위를 정해주었다. 그리고 알파벳을 방문한다면 visit 배열을 통해 방문체크를 해주었다. 만족하지 않는 경우는 2가지를 생각하였다. 첫째, 현재 알파벳보다 우선순위가 높은 알파벳인데 방문을 안했다면 거짓, 두번째, 현재 알파벳보다 우선순위가 낮은 알파벳인데 방문을 했다면 거짓. 이런식으로 접근하였다. 체크해야할 알파벳이 26개, 또한 문자열도 최대 26이므로 26*26 이 큰 숫자가 아니어서 단순히 접근하여 풀이를 하였다.

package programmers;
 
import java.util.ArrayList;
import java.util.List;
 
public class Solution_SummerWinter2018_스킬트리 {
    public static void main(String[] args) {
        String skill="CBD";
        String[] skill_trees= {"BACDE", "CBADF", "AECB","BDA"};
        
        System.out.println(solution(skill, skill_trees));
        
    }
    
    static int solution(String skill, String[] skill_trees) {
        int answer=0;
        
        int[] order = new int[26];
        
        for(int i=0;i<skill.length();i++) {
            order[skill.charAt(i)- 'A']=i+1;
        }
        
        boolean[] visit=new boolean[26];
        boolean isValid=true;
        for(String str : skill_trees) {
            
            for(int i=0;i<str.length();i++) {
                char curChar = str.charAt(i);
                if(skill.contains(curChar+"")==true) {    //스킬트리에 있는 문자열이면
                    for(int j=0;j<26;j++) {
                        //나보다 높은 우선순위이면서 방문안한경우
                        if(order[j]!= 0 && order[j] < order[curChar-'A'] && visit[j]==false) {
                            isValid=false; break;
                        }
                        //나보다 낮은 우선순위이면서 방문한경우
                        if(order[j]!= 0 && order[j] > order[curChar-'A'] && visit[j]==true) {
                            isValid=false; break;
                        }
                    }
                    
                    visit[curChar-'A']=true;
                }
                
                if(isValid==false) {
                    break;
                }
            }
            
            
            if(isValid==true)
                answer++;
            
            //초기화
            isValid=true;
            visit=new boolean[26];
        }
        
        
        return answer;
    }
}