[프로그래머스,Level 2] 스킬트리 (JAVA 구현)

- 첫 풀이 및 정답풀이

  이 문제를 처음 풀 때 든 생각은 skill_trees로 주어지는 문자열들의 한 글자를 기준으로 skill 문자열에서 해당 문자 이전의 모든 선행 스킬들의 방문 여부를 체크하고자 했다. 예를 들어 BACDE에서 첫 글자인 B는 1. skill 문자열에 포함되며, 2. 선행스킬인 C의 방문 여부를 체크 (여러 개면 모두 체크) 이와 같은 방식은 반복문을 3번이나 사용하고 코드 자체도 복잡해져 다른 방법을 생각해 보았다.

 

  다시 생각해본 풀이는 선행스킬만을 생각했을 때, 한 스킬을 배우기 이전의 스킬이 배워져 있다면 모든 선행 스킬이 모두 만족한 것이기 때문에 한 스킬의 이전 선행 스킬의 방문 여부만 체크하면 될 것 같다고 생각했다. 예를 들어 CBADF에서 C는 skill 문자열의 첫 번째 인덱스이므로 예외처리 후, 다음 글자인 B는 두 번째 인덱스이므로 선행스킬의 방문 여부를 확인한다. 이후 뒤에 나오는 D는 skill 문자열의 세 번째 인덱스이며, 이전 선행스킬인 B는 C를 배워야 배울 수 있기 때문에 C까지 고려할 필요가 없는 것이다. (말로 설명하기가 어렵지만, 코드를 보면 이해하기 쉬울 것이다.)

 

import java.util.Arrays;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        // 1. 초기 skill_trees의 크기가 반환할 수 있는 최댓값이다. 이후, 조건 불만족 시 차감.
        int answer = skill_trees.length;
        
        // 2. skill로 주어지는 선행스킬 방문여부를 관리 할 boolean 배열. A~Z까지 고려.
        boolean[] check = new boolean[27];
        
        // 3. skill_trees 탐색.
        for(int i = 0 ; i<skill_trees.length;i++){
            // 4. skill_trees의 문자열 요소들 탐색.
            for(int j = 0 ; j<skill_trees[i].length();j++){
                // 5. 선행스킬 정보인 skill에 존재하는 알파벳만 고려한다. 
                if(skill.contains(String.valueOf(skill_trees[i].charAt(j)))){
                    // 5-1. skill_trees의 문자열의 각 문자가 skill에 위치하는 인덱스를 반환.
                    int idx = skill.indexOf(skill_trees[i].charAt(j));
                    // 5-2. skill의 0번 인덱스는 무조건 가능, 해당 인덱스 이전인 선행스킬을 방문하지 않았다면,
                    if(idx != 0 && !check[skill.charAt(idx-1)-65]) {
                        // 5-2-1. 배울 수 없는 스킬이므로 answer 감소.
                        answer--;
                        break;
                    }
                    // 5-3. 나머지 경우는 조건을 만족하므로 true 처리.
                    else check[skill.charAt(idx)-65] = true;
                }                
            }
            // 6. 방문처리를 하는 배열을 다시 false로 초기화.
            Arrays.fill(check,false);            
        }
                      
        return answer;
    }
}