[Java/자바] 프로그래머스 Lv2 - 스킬트리 (정규식 사용)

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다.

따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

 

제한 조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 "CBD"로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

 

입출력 예

skill	skill_trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

 

입출력 예 설명

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

---

Solution.java

 

처음에는 이중 반복문을 통해서 풀다가 정규식을 통해 훨씬 효율적으로 풀 수 있는 방법을 알게 되었습니다.

먼저 skill_trees 배열의 스킬들을 선행 스킬의 문자열만 남도록 변환하고,

그 문자열이 선행 스킬의 순서가 저장되어있는 skill 문자열과 일치하는지 확인하는 방식을 통해

하나의 반복문을 사용하고 더욱 간결한 코드를 짤 수 있었습니다.

public class 스킬트리 {
    public static void main(String[] args) {
        System.out.println(solution("CBD", new String[]{"BACDE", "CBADF", "AECB", "BDA"}));
    }

    public static int solution(String skill, String[] skill_trees) {
        int answer = 0;

        for(int i = 0; i < skill_trees.length; i++) {
            // 정규식으로 선행 스킬들만 남은 문자열 생성
            String skillOrder = skill_trees[i].replaceAll("[^" + skill + "]", "");
            String requiredSkillOrder = skill.substring(0, skillOrder.length());

            if(skillOrder.equals(requiredSkillOrder)) {
                answer++;
            }
        }
        return answer;
    }
}

 

 

위 코드의 정규식 설명

"[^" + skill + "]"

[ ] 대괄호는 문자의 집합이나 범위를 나타내며 [abc]는 a, b, c 중 한 문자를 뜻합니다.

만약, [ ] 내에서 ^ 가 선행하여 존재하면 not을 나타냅니다.

즉, 해석하면 선행 스킬이 담긴 변수 "skill의 값 C, B, D 가 아닌 값을 찾겠다"는 뜻이 됩니다.

 

정규 표현식을 + 로 skill과 붙인 이유를 설명하자면

skill의 변수의 값을 사용해야하는데 + 로 정규 표현식과 skill 변수를 붙이지 않고

"[^skill]"으로 정규식을 사용할 경우 s, k, i, l, l 중의 문자가 아닌 값을 찾게 됩니다.

그러므로 + 를 통해 정규 표현식을 skill 변수와 붙여 사용해야합니다.

 

정규식에 대한 사용법이 좀 더 궁금하시다면 아래 링크를 참고해주세요.

[Java/자바] 정규식(Regular Expression) 사용법 총정리