프로그래머스 레벨2 - 스킬트리 with Java

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

 

제한 조건

스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
스킬 순서와 스킬트리는 문자열로 표기합니다.
예를 들어, C → B → D 라면 CBD로 표기합니다
선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
skill_trees는 길이 1 이상 20 이하인 배열입니다.
skill_trees의 원소는 스킬을 나타내는 문자열입니다.
skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

 

입출력 예

 

skill skill_trees return
"CBD" ["BACDE", "CBADF", "AECB", "BDA"] 2

 

입출력 예 설명

BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
CBADF: 가능한 스킬트리입니다.
AECB: 가능한 스킬트리입니다.
BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

 

나의 코드 1

public class Programmers_SkillTree {
    public static void main(String[] args) {
        String skill = "CBD";
        String[] skill_trees = {"BACDE","CBADF", "AECB","BDA"};
        
        //// 나의 첫 번째 풀이 ////
        int cnt = 0; // 선행 스킬에 해당하는 인덱스가 그 뒤의 스킬의 인덱스보다 작을 경우을 셀 변수
        int cntt = 0; // skill의 원소와 skill_trees의 원소가 같을 경우를 셀 변수
        int answer = 0;
        ArrayList<Integer> indexOfSkill = new ArrayList<>(); 
        	// skill tree에서 해당 skill이 있다면 그에 해당되는 인덱스를 저장할 ArrayList

        for(int j = 0; j < skill_trees.length; j++){
            String tree = skill_trees[j];
                for(int i = 0; i < skill.length(); i++) {
                    for(int h = 0; h < tree.length(); h++){
                        if(skill.charAt(i) == tree.charAt(h)) {
                            indexOfSkill.add(h); // 두 문자가 같을 경우 해당 인덱스 h를 추가
                            cntt += 1; // 횟수 추가
                        }
                        if(h == tree.length()-1 && cntt == 0){
                            indexOfSkill.add(30); // 한번도 같지 않았으면서 h가 마지막 인덱스일때 30을 추가
                        }
                    }
                    cntt = 0; // 초기화
                    if(i > 0 && indexOfSkill.get(i-1) < indexOfSkill.get(i))
                        cnt += 1; // 앞 스킬 인덱스와 비교하여 선행할 경우 cnt 추가
                }
                if(cnt == skill.length()-1) answer += 1;
                indexOfSkill.clear();
                cnt = 0;
        }
        System.out.println(answer);

 

 

해설

나는 왜이리 항상 코드를 복잡하게 짜는지 모르겠다. 

나는 항상 코테를 풀 때 백지에다 하나하나 따져가면서 이렇게 저렇게 하면 되겠다 라는 로직을 먼저 세운 후 코드를 짜는데 아마 그 과정에서부터 불필요한것들이 너무 많이 들어가는듯.

주어진 예시로 따져본 결과 skill에 주어진 스킬을 skill_trees의 스킬문자열의 문자들과 하나하나 비교해서 인덱스를 찾아 새로운 배열에 저장하고, 그 배열의 앞뒤를 비교해서 맞게 선행된것이 몇개인지를 세었을 때 그것이 그 배열 길이보다 -1이면 올바른 skill_tree라는 규칙을 발견했다.

처음에는 최근에 배운 hashmap을 사용해서 skill에 저장된 스킬 문자를 key로, skill_tree에 해당되는 스킬 문자의 인덱스를 value로 put해서 구하려했는데 해보면서 굳이 이렇게까지 안해도 되겠다는 생각이었다.

그래서 ArrayList에 인덱스를 집어넣는걸로 바꾼건데, 사실 그것도 필요 없는 것이었다.

무엇보다, 위의 코드로 하면 프로그래머스에서 테스트중 몇개만 통과한다 ㅠㅠ 고민해봐도 이유는 모르겠음...

 

그래서 다른분들의 코드를 참고해서 다시 짜봤다.

왠지 모르게 boolean 변수를 세우는것에 거부감이 있는데, 잘 활용하면 코드를 훨씬 효율적으로 짤 수 있을 것 같더라.

그리고 나처럼 굳이 ArrayList에 인덱스를 하나하나 저장하지 않고도 그냥 반복문 내에서 기다 아니다를 판단해서 바로 answer에 추가할 수 있게 했는데, 나도 굳이 인덱스를 따로 빼내서 저장하고, 그걸 또 다시 서로 비교하고 등등의 과정을 거치지 않고 cntt값을 가지고 바로 계산할 수 있었지 않을까 싶다.

 

 

나의 코드 2

public class Programmers_SkillTree {
    public static void main(String[] args) {
//// 다른이들의 답을 참고해 다시 푼 풀이 ////

        int answer = 0;

        for(int i=0; i<skill_trees.length; i++){
            boolean flag = true; // 제대로 된 스킬트리인지를 판별 및 초기화
            int skillIndex = 0; // skill 내의 스킬 인덱스에 따라 skill_trees의 해당 스킬들끼리의 인덱스를 구하기 위해, 및 초기화
            for(int j=0; j<skill_trees[i].length(); j++){
                for(int h=skillIndex; h<skill.length(); h++){
                	// h=skillIndex인 이유는, 밑에 else 구문에서 skillIndex가 1씩 증가하며 이미 지난 스킬을 체크했기 때문에, j++ 증감식이 수행된 후엔 그 다음 스킬부터 체크하면 되기 때문.
                    if(skill_trees[i].charAt(j)==skill.charAt(h)){
                        if(h!=skillIndex) flag = false;
                        // 만약 skill의 스킬 인덱스 h와 skill_tree에서 카운트한 skillIndex가 다르다면 flag를 false로
                        else skillIndex++;
                    }
                }
            }
            if(flag) answer++;
            // flag가 true일 경우 answer에 1 추가
        }
        System.out.println(answer);
    }
}

해설 및 후기

여러 코드들을 봤지만 이 코드가 가장 효율적이고 명확한 것 같아 로직을 이해한 후 코드를 보지 않고 다시 짜봤다.

처음에는 왜 세번째 반복문에서 h = skillIndex로 하는지, 그 밑 if문에서 if(h!=skillIndex)를 조건으로 주는지 이해가 안갔으나, 차근차근 i, j, h 등을 대입해보고 디버깅을 해보니 이해가 갔다.

 

예를들어 skill = "CBD" 이고 skill_trees[0] = "BACDE" 일 때,

세 번째 반복문에서 j=0, h=0부터 시작한다.

skill_trees[0].charAt(0) = B이므로 세 번째 반복문에서 이 B와 skill인 "CBD"를 하나씩 비교한다.

B - C 이므로 같지 않다. 패스. h++을 해주니 h=1이 된다.

B - B 이므로 같다. 같은데 h=1, skillIndex는 0이므로 같지 않으니 flag = false가 수행된다.

즉, skill_trees[0]에 B 전에 C가 나와서 skillIndex가 1이 되었어야 했는데 C가 선행되지 않았으니 이 트리는 안된다는 것.

B - D 이므로 같지 않다. 패스. h++을 해주니 h=2가 된다.

이렇게 j=0, h=0, 1, 2일때의 경우가 flag=false로 마무리된다.

 

그 뒤에 j=1, h=0, 1, 2일 때의 경우도 그대로 수행되고, flag가 true가 될 일은 없다.

한번 앞에서 false가 된 이상 다시 true로 초기화되는 지점이 skill_trees[1]로 넘어갈때기이 때문에, "BACDE" 내에서 수행되는 동안은 flag는 어차피 false.

 

그래서 skill_trees 내의 스킬트리들을 하나씩 검사한 후 flag가 true일때만 answer을 추가해주고, 그것을 반환해주면 된다.

 

어떻게 저런 생각을 했을까 싶기도 하지만서도, 내가 생각해내기 완전히 불가능한 건 아니라고 생각한다. 명심해야 할 것은, 너무 문과갬성으로 (문과입니다) 하나하나 다 출력하고 저장하고 하려하지 말고, 가장 효율적인 방안을 생각해 볼 것.