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

프로그래머스 level2 - 스킬트리 자바 풀이

---

 

 

 

프로그래머스

 

 

 

문제 요약

 

스킬을 한 시점에 하나 배울 수 있다.

 

연계 스킬들 정보가 주어지는데 연계 스킬들은 순서대로만 배울 수 있다.

 

연계 스킬이 아닌 스킬들은 언제든지 배울 수 있다.

 

연계 스킬 정보가 "ABC" 면  'C' 를 배우기 위해서는 'A , B' 를 배웠어야만 하는 이런 상태를 만족시켜서 스킬을 배웠는지 여부를 묻고 있다.

 

 

 

문제 풀이

 

사용자 스킬 스테이터스 저장소가 있다고 생각하고 저장소에 선행 스킬 정보가 있을 경우에만 다음 스킬을 배울 수 있다고 보면 될 것 같다.

 

 

 

연계스킬정보가 D -> A -> C 이고 다음과 같이 스킬 획득 요청이 있다고 생각해보자.

 

D는 선행스킬의 가장 첫 스킬이기 때문에 그냥 배울 수 있다.

 

 

요청은 C이고 배워야 할 스킬은 A이다.

 

연계 스킬트리 현황의 마지막 스킬이 D 이고 A는 없기 때문에 A를 배워야 하는 상황인데 요청은 C이기 때문에 잘못된 요청이다.

 

 

다음과 같은 획득 요청 순서였다면 배울 수 있을 것이다.

 

결국 사용자가 배웠던 스킬현황 목록들 중 가장 마지막 스킬이 무엇인지에 대해서 관심을 두고 그 다음 스킬이 무엇인지와 현재 배우고자 하는 스킬이 무엇인지를 비교해 모든 스킬 획득 요청에 대해 유효한지 검사할 수 있다.

 

따라서 스택이나 큐를 활용하면 쉽게 풀 수 있을 것 같다.

 

스택이라면 유효하면 넣고 검사할 때는 마지막 놈만 조회해와서 요청과 비교해 판단하면 된다.

 

큐라면 모든 연계 스킬 정보를 넣고 맨 앞의 스킬과 요청을 비교해 판단하고 큐에서 제거하면 된다.

 

 

스킬 학습에 있어 순서가 있다는 것을 응용해 큐나 반복을 활용하지 않고 문자열의 startWith 메소드를 활용해 매우 간단하게 풀어보았다.

 

 

 

 

 

연계스킬이 아닌 스킬 요청들만 다 필터링하고 남는 것들이 D이던 DA 이던 DAC 이던

 

주어진 DAC가 해당되는 요청으로 시작하는 문자열인지만 비교하면 유효하다는 것을 증명할 수 있다.

 

검사 불필요 스킬 문자 필터링은 정규식을 사용했다.

 

 

풀이 코드 

 

public static int solution(String skill, String[] skill_trees) {
    String regex = "[^" + skill + "]";
    return (int) Arrays.stream(skill_trees)
            .filter(tree -> skill.startsWith(tree.replaceAll(regex, "")))
            .count();
}

 

실질적인 검증을 위한 별도의 복잡한 과정을 따로 생각할 필요가 없게 된다.