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

---

온라인 문제풀이 사이트 Programmers의 '스킬트리' 문제.

https://programmers.co.kr/learn/courses/30/lessons/49993?language=java

문제는 간단하게 다음과 같다.

1. 스킬은 순서대로 배울 수 있다.

2. CBD가 입력으로 주어지면, C -> B -> D 순서로 배울 수 있다.

3. C를 배우지 않고 B나 D를 먼저 배울 수 없다.

4. 즉, 배우려면 앞에서부터 순서대로 배워야 하며 중간을 건너뛸수도 없다.

풀이 과정

가장 먼저 떠오른 방법은 Queue를 이용하는 것이다.

체크할 대상 문자열 배열(skill_trees)를 Queue에 넣고, 배울 수 있는 스킬 순서(skill)와 비교하는 방법이다.

그림으로 표현하면 아래와 같다.

문자열 BACDE의 문자 하나하나를 skill(CBD)와 비교해 skill에 포함되면 Queue에 넣고, 아니면 무시한다.

char temp = q.poll();
if(skill.contains("" + temp)) target += temp;

결국 최종 Queue에 저장된 BCD를 문자열로 만들어 skill(CBD)에 포함되는지 비교한다.

그리고 스킬을 배우려면 무조건 맨 앞에서부터 배워야 하므로, 0번째 index부터 시작했는지 비교한다.

if(skill.contains(target) && skill.charAt(0) == target.charAt(0)) answer ++;

결과는 Runtime Error가 났다.

아래는 전체 코드다.

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        for(int i = 0; i < skill_trees.length; i++) {
            String index = skill_trees[i];
            String target = "";
            
            for(int j = 0; j < index.length(); j++) {
                char charIndex = index.charAt(j);
                
                if(skill.contains(""+charIndex)) {
                    target += charIndex;
                }
            }            
            
            if(skill.contains(target) && skill.charAt(0) == target.charAt(0)) answer ++;
        }
        return answer;
    }
}

처음에는 이중 Loop문 때문에 Runtime Error가 나는 것이라고 생각했다.

하지만 input 최대 크기가 문자열 길이 26, 배열 길이 20 이므로

중첩 for문을 사용해도 시간 초과가 나지 않을텐데 이상했다.

주석으로 코드 일부를 제외하며 돌려본 결과,

if(skill.contains(target) && skill.charAt(0) == target.charAt(0)) answer ++;

이 조건문이 문제였다.

해당 조건문을 주석처리하자 런타임 에러 없이 실패 문구가 나왔다.

그래서 조건문을 다음과 같이 수정해 문제를 다시 채점했다.

if(target.equals(skill.substring(0, target.length()))) answer++;

어차피 맨 앞에서부터 스킬을 배워야 하기때문에 skill의 0번째 index부터 부분문자열인지 체크하면 됐다.

이번에는 중첩 loop문 없이 효율적인 코드 작성이 가능한지 확인하기위해 다른 방법을 시도해보았다.

시간 복잡도를 N*N에서 N으로 줄여보기 위함이다.

이를 위해서는 Queue가 필요했다.

public static int solution(String skill, String[] skill_trees) {
                
        int answer = 0;
        String strSum = "";
        Queue <Character> q = new LinkedList <Character>();
        
        int[] lengthOfArr = new int[skill_trees.length];
        
        for(int i = 0; i < skill_trees.length; i++) {
            strSum += skill_trees[i];
            lengthOfArr[i] = skill_trees[i].length();
        }
        
        char[] strSumToChar = strSum.toCharArray();
        
        for(int i = 0; i < strSumToChar.length; i++) {
            q.offer(strSumToChar[i]);
        }
        
        int targetLength = 0;
        String target = "";
        
        while(!q.isEmpty()) {
            
            char temp = q.poll();
            if(skill.contains("" + temp)) target += temp;
            
            if((--lengthOfArr[targetLength]) == 0) {
                if(target.equals(skill.substring(0, target.length()))) answer++;
                targetLength++;
                target = "";
            }
            
        }
        
        
        return answer;
    }

방식은 다음과 같다.

1. skill_trees 배열 각 index 문자열의 길이를 저장하는 정수형 배열을 만든다.(lengthOfArr)

2. skill_trees 배열의 모든 문자열을 이어붙인다.

3. 이어붙인 문자열을 Queue에 넣는다.

4. 한글자씩 빼면서 skill 문자열에 포함되는 문자인지 검사한다.

5. lengthOfArr 배열 index를 1씩 줄이고, 0이 되면 다음 index로 넘어간다.
다시 말해 각 index의 문자열을 이어붙였기 때문에 검사 완료 후 다음 문자열로 넘어간다는 소리다.

6. Queue가 비면 정답을 return한다.

실행 결과 비교샷

결과적으로 크게 다른 점이 없고, 심지어 몇몇 테스트케이스는 오히려 시간이 늘어난 것이 보였다.

중첩 Loop문을 제거하기 위해 조건문이 늘어나고, 배열과 큐를 추가로 더 사용했기 때문인 것 같다.