[프로그래머스] 스킬트리 (Level 2)

programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리

---

문제

스킬순서와 배워야하는 스킬트리가 주어진다

예를 들어,

skill : CBD

skill_trees : ["BACDE", "CBADF", "AECB", "BDA"] 이면,

스킬을 배울 때, 꼭 C, B, D 순서로 배워야만 한다

 

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

CBADF: 가능한 스킬트리입니다.

AECB: 가능한 스킬트리입니다.

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

 

그래서 스킬트리 중 총 2개를 배울 수 있다 

자세한 문제는 위 링크를 통해 확인할 수 있다

 

해결

우선 스킬순서를 map에 넣는다.

가장 마지막에 배워야하는 스킬을 1부터 시작해서 

가장 먼저 배워야하는 스킬은 skill.lengh 이다

그리고 나서 스킬트리에 있는 스킬들의 순서를 확인한다

map에 가장 먼저 배워야하는 스킬이 없으면 break

이전 스킬과 현재 스킬의 값 차이가 1이 아니면 break

이렇게 순서를 값으로 표현하여 풀어보았다

public class SkillTree {

    public static void main(String[] args) {
        String skill = "CBD";
        String[] skill_trees = {"BACDE", "CBADF", "AECB", "BDA"};
        solution(skill, skill_trees);
    }

    public static int solution(String skill, String[] skill_trees) {
        Map<Character, Integer> map = new HashMap<>();
        char[] skillArray = skill.toCharArray();
        for (int i=0; i<skillArray.length; i++) map.put(skillArray[i], skillArray.length-i);

        int count = 0;
        for (String s : skill_trees) {
            int before = 0;
            char[] charArray = s.toCharArray();
            for (int i=0; i<charArray.length; i++) {
                if (map.containsKey(charArray[i])) {
                    if (before == 0) {
                        if (charArray[i] != skillArray[0]) break;
                        before = map.get(charArray[i]);
                    } else {
                        int sum = before - map.get(charArray[i]);
                        before = map.get(charArray[i]);
                        if (sum != 1) break;
                    }
                }
                if (i == charArray.length-1) count++;
            }
        }

        return count;
    }
}