🎯문제
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 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 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.
스킬 트리: 유저가 스킬을 배울 순서 ↩
✏️풀이
코드
class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
for(int i = 0; i < skill_trees.length; i++) {
StringBuilder stb = new StringBuilder();
// 스킬트리 길이만큼 반복
for(int j = 0; j < skill_trees[i].length(); j++) {
// 스킬을 하나씩 나눠줌
String temp = skill_trees[i].substring(j, j + 1);
// skill에 포함이 된다면 StringBuilder를 사용해 저장
if(skill.contains(temp)) {
stb.append(temp);
}
}
// 저장된 값을 String으로 변환한 뒤 사용 가능여부 판단
if(skill.startsWith(stb.toString())) {
answer++;
}
}
return answer;
}
}설명
선행 스킬 트리가 주어져있고, 해당 선행 스킬 트리를 사용할 수 있는 스킬 트리의 개수를 구하는 문제였다. 따라서 스킬 트리 배열에 저장된 값을 하나하나 확인하는 것이 필요하다고 생각이 들었다.
스킬 트리를 반복하는데 스킬을 하나씩 확인하면서 선행 스킬 트리에 포함이 되는 스킬이라면 StringBuilder를 사용해서 값을 저장해주었다. String 변수를 하나 만들어서 저장을 해도 통과가 되지만 직접 해보니 시간의 차이가 꽤 났다. 기왕 푸는 거 효율이 좋은 방식으로 풀어보자는 생각에 StringBuilder를 사용해서 풀어보기로 했다.
스킬을 하나씩 나눠주는 것은 substring을 사용하였다. 이를 통해 contains 함수를 사용하여 스킬이 선행 스킬에 포함이 된다면 StringBuilder에 저장을 하고 반복문을 빠져나오게 되면 저장된 값을 String으로 변환한 뒤에 사용 가능 여부를 판단한다.
사용 가능 여부는 스킬을 모두 배우는 것의 여부가 아니라 배우는 순서가 올바른지 판단하는 것이다. 때문에 startsWith 을 사용하여 StringBuilder에 저장된 값이 선행 스킬 트리의 순서와 맞는지 판단해주었다.
해당 판단 여부를 통해 사용할 수 있다면 answer 값을 증가해주고 위의 과정을 다시 반복한다. 해당 반복이 끝난 뒤 answer를 반환해주면 해결할 수 있다!
💡느낀 점
이전에 있던 문제들보다는 훨씬 빠른 시간에 풀 수 있던 문제였다. 다행히 아이디어가 좋은 방향으로 생각이 났던 것 같다. 처음 문제를 풀었을 때는 substring, startsWith 같은 함수들을 잘 몰랐는데, 한번 사용해보고 나니 매우 잘 사용하고 있다 :) 아이디어 뿐만 아니라 함수를 적절하게 사용하는 것도 문제를 푸는데 많은 도움이 되는 것을 알게 해준 문제였다.
링크
