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

 

https://programmers.co.kr/learn/courses/30/lessons/49993#fn1

코딩테스트 연습 - 스킬트리

[문제]

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

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

 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

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

 

[제한 조건]

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

 

[코드]

class Solution {
    public int solution(String skill, String[] skill_trees) {
	     int answer=skill_trees.length;
	     int before=0; 
	     int current=0;
	     
	     for(int i=0;i<skill_trees.length;i++) {
	    	 /*
	    	  *  before에는 skill의 첫 번째 알파벳이 skill_trees[i]의 
	    	  *  몇 번째 인덱스에 있는지 저장되어 있다.
	    	  *  
	    	  *  예를들어 skill이 CBD이고, skill_tree[i]가 BACDE라면 
	    	  *  before에는 BACDE에 C가 몇 번쨰 인덱스에 있는지가 저장되어 있는 것이다.(=2)
	    	  */
	    	 before=skill_trees[i].indexOf(skill.charAt(0));
	    	 
	    	 // skill의 첫 번쨰 인덱스는 이미 before에 저장되어 있으므로 다음 문자부터 검사
	    	 for(int j=1;j<skill.length();j++) {
	    		 // 현재 비교하고자 하는 skill의 알파벳이 몇 번쨰에 있는지 검사
	    		 current=skill_trees[i].indexOf(skill.charAt(j));
	    		 
	    		 /*
	    		  * 현재 구하고자 하는 스킬이 스킬트리에 있고, 
	    		  * 이전 스킬의 인덱스가 현재 스킬의 인덱스보다 크다면 불가능
	    		  * -> 예를들어 skill이 CBD이고, skill_tree[i]가 BACDE라면 
	    		  * C의 인덱스는 2, B의 인덱스는 0인 경우
	    		  * 
	    		  * 또한 이전 스킬이 스킬트리에 없는데 현재 스킬이 스킬트리에 있다면 불가능
	    		  * -> 예를들어 skill이 CBD이고, skill_tree[i]가 AEBFG라면
	    		  * C의 인덱스는 -1(스킬트리에 포함X), B의 인덱스는 2이인 경우
	    		  */
	    		 if((before>current&&current!=-1)||(before==-1&&current!=-1)) {
	    			 answer--;
	    			 break;
	    		 }
	    		 before=current; // 값 갱신
	    	 }
	     }
	     
	     return answer;
	 }
}

 

[고찰]

 이번 문제를 푸는데 오랜 시간이 걸렸다. 아직 로직을 짜는 것과 모든 예외 상황을 고려하는 부분이 미숙해서 그런것 같다. 많은 문제를 푸는 것도 중요하지만 밀도 있는 문제를 스스로 구현하는 것이 더 중요하다는 것을 다시 한번 느꼈다.

<문자열 함수> String.indexof("문자") : 해당 문자가 String의 몇 번째 인덱스에 위치하는지 반환하는 함수. 만약 문자를 포함하고 있지 않다면 -1 반환