skill_tree

스킬 트리

• 문제

• 간단한 문제 설명
  문자열 skill과 문자열 배열 skill_trees가 주어진다. skill에 있는 문자들을 스킬이라고 했을 때 각 문자는 다음 문자의 선행 요소가 된다. 예를 들어 skill="ABC"이면, B 이전에 A가 있어야 하고 C 이전에 B가 있어야 한다. skill_trees에는 여러 스킬 트리가 있는데 주어진 skill을 만족하는 스킬 트리가 몇개인지 반환하는 문제이다. 스킬 트리에서 skill에 없는 문자는 선행 요소에 영향을 받지 않는다.

• 내 코드

• 내 코드 설명
  두 가지 방법이 있다. 첫 번째 방법은 check 함수이다.
  skill 크기 만큼의 정수형 배열(tmp)을 만들고 skill의 첫 번째 문자부터 마지막 문자까지 스킬 트리에 있는지 탐색하여 인덱스를 tmp에 저장한다. String의 indexOf 메서드는 해당 문자가 있다면 해당 문자의 위치 인덱스를 반환하지만 없다면 -1을 반환한다. skill의 두 번째 문자부터는 스킬 트리에 해당 문자가 있고 바로 앞 문자가 스킬트리에 있다면 바로 앞 문자가 스킬 트리에 위치한 인덱스가 해당 문자가 위치한 인덱스보다 작은 값인지 검사한다. 스킬 트리에 해당 문자가 있는데 바로 앞 문자가 스킬 트리에 없다면 스킬 트리는 skill을 만족하지 못하며, 바로 앞 문자가 위치한 인덱스의 값이 해당 문자 인덱스보다 큰 값이라면 스킬 트리가 skill을 만족하지 못한다. 이렇게 스킬 트리를 검사하여 skill을 만족하는 스킬 트리의 개수를 반환한다.
  두 번째는 방법은 check1 함수이고 다른 분들의 풀이 보고 알게된 방법이다.
  스킬 트리의 문자열을 replaceAll 메서드를 사용해 skill에 있는 문자 외의 문자를 ""로 바꾼다. 이렇게 하면 각 스킬 트리는 skill에 있는 문자만 남게되고, indexOf 메서드를 사용해 스킬 트리의 문자가 skill에 위치한 인덱스를 얻을 수 있다. 스킬 트리가 skill을 만족해야하기 때문에 인덱스가 0이 아니면 스킬 트리는 skill을 만족하지 않는다. 예를 들어 skill="ABC", 스킬 트리="REBHSC"라면 스킬 트리에 replaceAll을 사용하면 "BC"만 남는다. skill.indexOf("BC")=1 이며, 이 결과는 B 이전에 A 선행 요소가 있지 않다는 의미이며 스킬 트리는 skill을 불만족한다.

• 결과
  첫 번째 방법이 두 번째 방법보다 실행 속도는 빠르다.

  첫 번째 방법

  테스트 1 〉	통과 (0.83ms, 52.2MB)
  테스트 2 〉	통과 (0.82ms, 52.4MB)
  테스트 3 〉	통과 (0.86ms, 50.2MB)
  테스트 4 〉	통과 (0.81ms, 50.4MB)
  테스트 5 〉	통과 (0.87ms, 52.4MB)
  테스트 6 〉	통과 (0.78ms, 50MB)
  테스트 7 〉	통과 (0.86ms, 52.7MB)
  테스트 8 〉	통과 (0.86ms, 53.1MB)
  테스트 9 〉	통과 (0.84ms, 52.6MB)
  테스트 10 〉	통과 (0.84ms, 52.1MB)
  테스트 11 〉	통과 (0.86ms, 53.1MB)
  테스트 12 〉	통과 (0.84ms, 50.8MB)
  테스트 13 〉	통과 (0.74ms, 50.3MB)
  테스트 14 〉	통과 (0.81ms, 52.8MB)
  

  두 번째 방법

  테스트 1 〉	통과 (19.75ms, 54.7MB)
  테스트 2 〉	통과 (19.46ms, 54.2MB)
  테스트 3 〉	통과 (18.99ms, 54.5MB)
  테스트 4 〉	통과 (18.79ms, 52.6MB)
  테스트 5 〉	통과 (19.42ms, 52.5MB)
  테스트 6 〉	통과 (18.37ms, 54.2MB)
  테스트 7 〉	통과 (19.89ms, 54.8MB)
  테스트 8 〉	통과 (19.72ms, 52.6MB)
  테스트 9 〉	통과 (19.52ms, 54.6MB)
  테스트 10 〉	통과 (19.85ms, 54.3MB)
  테스트 11 〉	통과 (21.06ms, 52MB)
  테스트 12 〉	통과 (20.50ms, 54.4MB)
  테스트 13 〉	통과 (20.39ms, 54.3MB)
  테스트 14 〉	통과 (18.38ms, 54.6MB)