스킬트리

Posted on Edited on In , ,

문제정의

스킬트리의 순서를 만족하는 문자열이 몇개가 되는지 반환하는 문제이다. 롤에서 먼저가야할 템트리를 생각하면 쉬울 것 같다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;

public class SkillTree {

    //프로그래머스 문제풀이 level2 스킬트리

    public static void main(String[] args)
    {
        String skill = "CBD";
        String[] skill_trees = {"BACDE", "CBADF", "AECB", "BDA"};
        int answer = 0;
        boolean isAdd = true;
        HashMap<Character, Integer> map = new HashMap<>();
        char[] skill_arr = skill.toCharArray();
        int v = 0;
        for(char c : skill_arr)
        {
            map.put(c, v);
            v++;
        }
        for(String s : skill_trees)
        {
            int pre_v = -1;
            char[] skill_tree_arr = s.toCharArray();
            for(char c : skill_tree_arr)
            {
                int value = map.getOrDefault(c, -1);
                if(value != -1 && value - pre_v != 1)
                {
                    isAdd = false;
                    break;
                }
                else if(value != -1)
                    pre_v = value;
            }
            if(isAdd)
                answer++;
            isAdd = true;
        }
        System.out.print(answer);
    }
    
}

필자는 해시를 이용하여 문제를 풀었다. 자세한 사항은 부분부분 보면서 따라가자. 
1
2
3
4
5
6
7
8
9
boolean isAdd = true;
HashMap<Character, Integer> map = new HashMap<>();
char[] skill_arr = skill.toCharArray();
int v = 0;
for(char c : skill_arr)
{
    map.put(c, v);
    v++;
}
isAdd는 문자열이 조건을 만족하는지 여부를 저장하는 변수이다. 해쉬를 쓰기 위해 해시 맵을 선언했다. skill의 문자 하나하나를 hash에 매핑 시킨다. 예를 들어 "CBD"가 주어진다면, [C:0, B:1, D:2]와 같이 매핑된다. 이렇게 매핑해두면 각 키의 값을 비교하여 1씩 증가하는 지 확인하면 된다. 매핑하지 않은 키는 -1을 반환하도록 하여 이 연산에서 빠지도록 한다. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for(String s : skill_trees)
{
    int pre_v = -1;
    char[] skill_tree_arr = s.toCharArray();
    for(char c : skill_tree_arr)
    {
        int value = map.getOrDefault(c, -1);
        if(value != -1 && value - pre_v != 1)
        {
            isAdd = false;
            break;
        }
        else if(value != -1)
            pre_v = value;
    }
    if(isAdd)
        answer++;
    isAdd = true;
위에서 설명한 부분의 코드이다. pre_v의 초기값으로 -1을 넣어준 뒤, 주어진 스킬트리에서 문자를 하나씩 꺼내본다. 만약 맵에 있는데 초기값과 1차이가 나지 않는다면, 조건을 만족하지 않으므로 isAdd를 false하고 반복문을 탈출한다. 맵에 있는 값이면 pre_v를 업데이트 해주는 것을 잊지 않도록 하자. 다음엔 isAdd를 통해 정답을 세나간다. 최종적인 시간복잡도를 계산해보면 skill_trees의 길이를 n이라하고 skill_trees에 있는 문자열의 길이를 m이라하면, \(O(n*m)\)이다.

테스트



정규식을 통해 문제를 푼 사람도 있어서 신기했다. skill_trees의 각 원소에서 skill이 아닌 문자들을 지운뒤, indexOf를 활용하여 순서를 유지하는지 확인하였다. 이럴 경우 코드 수가 많이 줄어들어 가독성이 좋았다. 나도 정규식을 좀 더 공부해 봐야겠다.