[프로그래머스] - 스킬트리

문제

 

조건

 

입출력 예제

 

솔루션

• 본인이 생각한 방법은 아래와 같다.

1. 모든 문자열이 알파벳 대문자로만 구성되어 있으므로, 길이가 26 (알파벳 갯수) 인 boolean 배열을 만들어서 처리해보자.
2. 유저들이 만든 스킬트리의 문자를 조회하며, 이 스킬이 가능한지를 possible 배열을 조회한다. 
3. 가능하다면 문자열 끝까지 여부를 확인하고, 가능하지 않다면 중단한다.

코드 설명

1. 길이 26의 배열 possible을 만들고, 모두 true로 초기화한다.
2. skill (순서가 정해진 스킬) 의 첫 번째 문자를 제외하고 나머지 skill 문자의 possible을 false로 바꾼다.
3. skill_trees (유저가 만든 스킬트리) 길이만큼 반복문을 수행한다.
   1. ispos는 스킬트리가 가능한지 여부를 체크하는 변수이며, cppossible은 각 유저 스킬트리를 확인하기 위해 possible을 복사한 배열이며, idx는 정해진 스킬인 skill의 문자를 순서대로 조회하기 위한 인덱스이다.
   2. cppossible[skill_trees[i] - 'A'] 가 가능할때 (true 일때), 이 문자가 skill[idx]와 일치하고, idx가 skill의 끝부분이 아니라면, idx를 1 증가시키고, 1 증가시킨 idx (다음 인덱스) 의 cppossible[skill[idx] - 'A']를 false -> true로 갱신한다.
   3. cppossible이 false라면 (가능하지 않다면), ispos = false로 갱신하고 반복문을 빠져나간다.
4. ispos == true (스킬트리가 가능하다면), answer (갯수) 를 1증가시킨다.

 

• 정규표현식을 통해서 더 간단하게 문제를 해결할 수 있는 방법이 있으니 정규표현식 공부.

 

Code

• 전체 코드 : https://github.com/SubAkBa/Algorithm_Chung_Son/blob/master/Programmers/Solution_skillstreat.java

 

결과