Lv 2. 스킬트리

 

코드 흐름

• 우선 스킬트리를 역순으로 비교하였다. 스킬트리의 최종스킬의 인덱스는 중간 스킬의 인덱스 보다 커야만 성립하기에 각 유저의 스킬트리를 forEach문으로 들고왔다.
• 그리고 그 스킬트리를 검사하는데 필요한 변수들을 선언하고
• skill의 스킬트리에 반하지 않는지 검사하기위해 while문으로 skill.length가 --를 거듭한 끝에 -1이 되기 전까지 루프를 열어주었다.
• indexOf와 valueOf charAt 메서드를 이용하여 스킬트리에 반하는 조건이 존재하는지 확인하였다.
• 최종적으로 A->B->C 순으로 스킬트리를 진행하여야 할 때 A를 배우지 않고 B,C를 차례로 배우는 경우의 수에서 통과되는 오류가 발생하여 checkTree() 메서드로 유효성 검사를 한번더 진행후 answer 갯수를 더 해주었다.

import java.util.*;

class Solution {
    boolean[] learn;
    public boolean checkTree(int size){
        boolean check = true;
        for(boolean b : learn){
            if(check && !b)
                check=false;
            else if(!check && b)
                return false;
        }
        return true;
    }
    public int solution(String skill, String[] skill_trees) {
        int answer = 0, where;
        for(String str : skill_trees){
            int length = skill.length()-1;
            int down = Integer.MAX_VALUE;
            boolean isVaild = true;
            learn = new boolean[skill.length()];
            while(length!=-1){
                char now = skill.charAt(length); 
                if(str.indexOf(String.valueOf(now))!=-1){
                    where = str.indexOf(String.valueOf(now));
                    learn[length] = true;
                    if(where < down)
                        down = where;
                    else {
                        isVaild = false;
                        break;
                    }
                }
                length--;
            }
            if(isVaild && checkTree(skill.length()))
                answer++;
        }
        return answer;
    }
}

하지만 이는 유효성 검사로 인해 보다 효율성이 떨어지는것 같아 다른사람의 풀이를 보았고 나보다 효율적인 코드를 발견후 포스팅 한다.

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        for (String skillTree : skill_trees) {
            int learningIdx = 0;
            boolean isAble = true;
            for (char curSkill : skillTree.toCharArray()) {
                int skillIdx = skill.indexOf(curSkill);
                if (skillIdx == -1)
                    continue;
                else if (skillIdx == learningIdx)
                    learningIdx++;
                else {
                    isAble = false;
                    break;
                }
            }
            if (isAble)
                answer++;
        }
        return answer;
    }
}

 

이 코드는 역순이 아닌 차례대로 검사를 진행하고 있었고 learning idx 변수를 통하여 유효성검사까지 진행이 되고있었다. 
그리하여 루프를 2번 돌릴 이유가 없었으며 사용된 메모리와 시간복잡도 면에서 내코드보다 우수했다.

이처럼 남의 코드를 보는것은 정말 큰 도움이 되고 사고의 다양성을 늘려주는것 같다.