[49993] 스킬트리

✔ 스킬트리

[프로그래머스 49993]

문제 분석하기

해시맵에 선행 스킬과 선행 스킬 순서 인덱스를 저장한 후,

유저들이 만든 스킬트리를 보면서 현재 유저의 스킬 레벨이 스킬을 배우기 위한 선행 스킬 레벨과 같지 않다면 불가능

 

예) 선행 스킬 : "CBD", 유저들이 만든 스킬트리 : ["BACDE", "CBADF"]

skillBook : {"C:1", "B:2", "D:3"}

유저 1
현재 스킬 레벨	배울 스킬 트리의 선행 스킬 레벨	스킬 배우기 여부
0	B → 2 - 1 = 1	X

유저 2
현재 스킬 레벨	배울 스킬 트리의 선행 스킬 레벨	스킬 배우기 여부
0	C → 1 - 1 = 0	O 스킬 레벨 업
1	B → 2 - 1 = 1	O 스킬 레벨 업
2	A → 선행 스킬 X	O
2	D → 3 - 1 = 2	O 스킬 레벨 업
3	F → 선행 스킬 X	O

손으로 풀어보기

1. 해시맵에 선행 스킬과 선행 스킬 순서 인덱스를 저장
2. 유저들이 만든 스킬트리를 보면서 현재 스킬에 선행 스킬이 존재하는지 확인
   • 선행 스킬이 존재하지 않는다면 배울 수 있음
   • 선행 스킬이 존재하며 현재 선행 스킬 레벨과 같다면 배울 수 있으므로 스킬 레벨 업
   • 선행 스킬이 존재하며 현재 선행 스킬 레벨과 다르다면 선행 스킬을 배우지 않은 것이므로 배울 수 없음
3. 가능한 스킬트리 개수 반환

슈도코드 작성하기

skill(선행 스킬 순서)
skill_trees(유저들이 만든 스킬트리)
answer(가능한 스킬트리 개수)
map(선행 스킬트리 북)
선행 스킬트리 북 만들기 함수(skill)
for(s -> skill_trees만큼) {
    if(스킬 순서 확인 함수(s))
        answer 증가
}
answer 반환

선행 스킬트리 북 만들기 함수 {
    for(i -> skill의 길이만큼) {
        map에 스킬과 스킬 순서 인덱스를 저장
    }
}

스킬 순서 확인 함수 {
    level(현재 스킬 레벨)
    for(i -> skill_tree의 길이만큼) {
        c(현재 배울 스킬)
        if(c를 배우기 위해서 선행 스킬이 필요하다면) {
            if(level과 c의 선행 스킬 레벨이 같다면)
                배울 수 있으므로 level을 c의 스킬 레벨로 변경
            else
                배울 수 없으므로 false 반환
        }
    }
    true 반환
}

코드 구현하기

/**
 * 49993) 스킬트리
 */
public class L052_49993 {
    // map(선행 스킬트리 북)
    Map<Character, Integer> map = new HashMap<>();

    // skill(선행 스킬 순서)
    // skill_trees(유저들이 만든 스킬트리)
    public int solution(String skill, String[] skill_trees) {
        // answer(가능한 스킬트리 개수)
        int answer = 0;
        // 선행 스킬트리 북 만들기 함수(skill)
        makeSkillBook(skill);
        for (String s : skill_trees) {
            // 스킬 순서 확인 함수(s)가 true라면
            if (isCorrect(s))
                // answer 증가
                answer++;
        }
        // answer 반환
        return answer;
    }

    // 선행 스킬트리 북 만들기 함수
    private void makeSkillBook(String skill) {
        // map에 스킬과 스킬 순서 인덱스를 저장
        for (int i = 0; i < skill.length(); i++) {
            map.put(skill.charAt(i), i + 1);
        }
    }

    // 스킬 순서 확인 함수
    private boolean isCorrect(String skill_tree) {
        // level(현재 스킬 레벨)
        int level = 0;
        for (int i = 0; i < skill_tree.length(); i++) {
            // c(현재 배울 스킬)
            char c = skill_tree.charAt(i);
            // c를 배우기 위해서 선행 스킬이 필요하다면
            if (map.containsKey(c)) {
                // level과 c의 선행 스킬 레벨(c의 스킬 레벨 - 1)이 같다면
                if (level == map.get(c) - 1)
                    // 배울 수 있으므로 level을 c의 스킬 레벨로 변경
                    level = map.get(c);
                // level과 c의 선행 스킬 레벨이 다르다면
                else
                    // 배울 수 없으므로 false 반환
                    return false;
            }
        }
        // true 반환
        return true;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L052_49993 solution = new L052_49993();

        String skill = "CBD";
        String[] skill_trees = { "BACDE", "CBADF", "AECB", "BDA" };

        int result = solution.solution(skill, skill_trees);

        System.out.println(result);
    }
}