2018 윈터코딩 스킬트리

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리 | 프로그래머스

나의 풀이

Skill	Skill_Trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

 

- Skill을 Queue에 담고, Skill_Trees에서 해당하는 게 있을 때 poll 해준다.

 

위의 예시에서 처음 Skill_Tree인 BACDE인 경우에 

 

B를 가지고 Skill에 있는지 확인한다. 

 

B는 CBD에 있는 문자이기 때문에 Queue에 있던 Skill을 poll 한다.

 

이때 poll 한 값과 처리 중인 값을 비교한다. ( poll 값 : C , 처리 중인 값 : B )

 

두 값이 같지 않다면, C보다 B가 먼저 나왔으므로 잘못된 스킬 트리이다.

 

두 번째 CBADF인 경우에

 

C가 CBD에 있으므로  ( poll 값 : C , 처리 중인 값 : C )

B가 CBD에 있으므로  ( poll 값 : B , 처리중인 값 : B )

A는 없으므로 넘어간다.

D는 CBD에 있으므로  ( poll 값 : D , 처리중인 값 : D )

 

이렇게 순차적으로 진행이 되기 때문에 올바른 스킬 트리이다.

코드

package Programmers;
 
import java.util.LinkedList;
import java.util.Queue;
 
public class SkillTress {
 
    public static void main(String[] args) {
 
        String skill = "CBD";
        String[] skill_trees = {
                "BACDE", "CBADF", "AECB", "BDA"
        };
 
        int answer = solution( skill , skill_trees);
 
        System.out.println(answer);
 
    }//main
 
    public static int solution(String skill, String[] skill_trees) {
 
        int answer = 0;
        
        char[] skillBox = skill.toCharArray();
        
        
        for ( int i = 0 ; i < skill_trees.length; i ++ ) {
            
            char[] skTr = skill_trees[i].toCharArray();
            
            Queue<Character> q = new LinkedList<Character>();
            
            for ( int r = 0 ; r < skillBox.length; r ++ ) {
                q.add(skillBox[r]);
            }
            
            boolean possible = true;
            
            // 배우는 스킬에 선행스킬이 있는지 확인한다.
            for ( int j = 0 ; j < skTr.length; j ++ ) {
                
                char s1 = skTr[j];
                
                for ( int k = 0 ; k < skillBox.length; k ++ ) {
                    if( s1 == skillBox[k] && s1 != q.poll() ) {
                        possible = false;
                        break;
                    }
                }
                if ( !possible ) break ;
            }
            
            if ( possible ) answer++;
        }
        
        return answer;
 
    }//soultion
 
}//class
 

제출 결과

추가풀이

프로그래머스에서 다른 사람의 풀이를 보았더니 indexOf와 replaceAll과 정규식을 사용해서 간결하게 풀어냈다.

 

1. 입력문자에서 Skill에 해당하지 않는 값들은 모두 공백으로 바꾼다. ( 정규표현식을 사용해서 )

 

BACDE의 경우 BCD가 남게 된다. 

 

2. Skill.indexOf()를 수행해서 0이 아닌 경우는 모두 삭제해 준다. ( ArrayList에서 remove 해준다. )

 

3. 최종 ArrayList의 사이즈를 출력한다.