코딩테스트 연습 / Summer/Winter Coding(~2018) / 스킬트리 / JAVA

 

풀이 방법1

import java.util.LinkedList;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        
        char[] s = skill.toCharArray();
        LinkedList<Character> list = new LinkedList<Character>();
        
        for(int i=0; i<skill_trees.length; i++) {
        	
            for(int j=0; j<s.length; j++) {
                list.add(s[j]);
            }
        	
            boolean b = true;
        	
            for(int j=0; j<skill_trees[i].length(); j++) {
        		
                if(!list.isEmpty() && skill_trees[i].charAt(j) == list.getFirst()) list.removeFirst();
                    else {
                        for(int k=0; k<list.size(); k++) {
                            if(skill_trees[i].charAt(j) == list.get(k)) {
                                b = false;
                                break;
                            }
                        }
                }
        		
                if(!b) break;
            }
        	
            list.clear();
            if(b) answer++;
        }
        
        return answer;
    }
}

문제 자체는 RPG 게임 한 번이라도 해본 사람은 재미있게 읽었을 것 같습니다.(읽기만 재밌음) 

위의 풀이는 LinkedList를 이용한 풀이입니다.

 

처음에는 테스트 케이스 skill인 BCD가 전부 들어와야 되는줄 알고 배열로 접근했다가

B나 BC만 들어오는 경우도 생각해야 된다는 점을 간과했습니다.

 

그래서 큐로 문제를 접근하려고 시도했습니다.

큐로 문제를 풀때는 접근방식을 다르게 하여 B, BC, BCD가 아닌 경우를 찾아서 제거시키는 방향으로 생각해보았습니다.

그러나 큐는 앞뒤만 삭제가 되는 자료구조 이므로 BD인 경우가 통과되는 경우가 발생했습니다.

 

그래서 LinkedList를 이용했습니다.

처음에 새로운 스킬 트리가 입력되면 스킬 list를 채워주고

스킬 트리안의 내용물을 하나하나 검사합니다. 만약 B보다 C나 D가 먼저 들어온다면 remove 시키고 break 해줍니다.

(remove 안해도 어차피 break로 반복문을 탈출하므로 지웠습니다 // 아래 히스토리 참고)

 

중요한 점은 boolean을 사용해서 B보다 먼저 사용되는 스킬이 있을 경우 false로 바꿔줘서 answer를 올리지 못하도록 막아줍니다.

그리고 마지막으로 한 스킬트리의 검사가 끝나면 이전에쓰던 스킬트리의 list가 반영되면 안 되므로 list를 clear()시켜줍니다.

 

 

풀이 방법2

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = skill_trees.length;
        
        for(int i=0; i<skill_trees.length; i++){
            if(skill.indexOf(skill_trees[i].replaceAll("[^"+skill+"]",""))!=0) {
                answer--;
            }    
        }
        
        return answer;
    }
}

정규식을 이용한 풀이입니다.

프로그래머스에 어떤분이 풀이한것을 조금 리팩토링해봤습니다.

보통 skill을 skill_trees에 맞추려고 문제를 접근하는데

역발상을 했다는 점에서 굉장히 수준 높은 코드라는 생각이 들었습니다.

 

이 풀이는 skill_trees에 skill을 맞추려기 보다는

skill에 없는 문자열들을 skill_trees에서 전부 공백문자열로 바꿔준다음

skill에 skill_trees의 맨앞 문자열이 skill의 맨앞문자열과 같은지를 비교해주는 풀이방법입니다.

 

그러나 Iterator와 정규식 등 다소 무거운 코드들을 사용했기 때문인지

간결하지만 수행속도는 조금 떨어지길래 Iterator를 for문으로 바꾸고 불필요한 ArrayList를 제거하여

좀 더 간결하게 바꿔봤습니다.

 

 

수행 속도 비교

	풀이 방법 1	풀이 방법2
1차 수행 속도	825,700	1,331,700
2차 수행 속도	810,400	1,251,500
3차 수행 속도	838,100	1,331,500
평균 수행 속도	약 824,733	약 1,304,900

 

 

히스토리

chucoding/algorithm