문제
https://school.programmers.co.kr/learn/courses/30/lessons/49993
입력
- 선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees
출력
- 가능한 스킬트리 개수
풀이
제한조건
- 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
- 스킬 순서와 스킬트리는 문자열로 표기합니다.
- 예를 들어, C → B → D 라면 "CBD"로 표기합니다 - 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
- skill_trees는 길이 1 이상 20 이하인 배열입니다.
- skill_trees의 원소는 스킬을 나타내는 문자열입니다.
- skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.
접근방법
단순 구현(문자열)
언뜻 보기에는 위상정렬을 사용하는 문제처럼 보일 수 있다.
하지만 자세히 본다면 단순 문자열 처리로 풀 수 있다.
문제를 가장 단순하게 이해해 본다면,
skill로 주어지는 문자열의 순서를 skill_trees의 원소가 지키고 있는것인가 이다.
입력 예시를 살펴보자.
skill : "CBD"
skill_trees : ["BACDE", "CBADF", "AECB", "BDA"]C의 인덱스 < B의 인덱스 < D의 인덱스를 만족시키면 가능한 스킬트리이다.
Java의 경우, String class의 indexOf() 함수를 이용하여 특정 글자가 가장 처음 등장하는 index를 얻을 수 있다.
이를 바탕으로 비교하면 된다.
주의할점은 만약 예제의 B 처럼 중간에 등장하는 문자가 존재하지 않을 경우, index 정보를 최대치로 할당해주면 된다.
B의 다음에 존재하는 스킬의 경우, B가 없으면 배울 수 없기 때문에 index값 처리에 신경을 쓰도록 하자.
코드
class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
char[] cstr = skill.toCharArray();
for(String s : skill_trees){
int base = -2;
boolean flag = true;
for(char c : cstr){
int next = s.indexOf(c);
if(next == -1) // 다음에 나오는 스킬들은 모두 배울 수 없다.
next = Integer.MAX_VALUE;
if(base > next){
flag = false;
break;
}
base = next;
}
if(flag)
answer++;
}
return answer;
}
}