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

 

로직

탐색하려는 letter가 현재 skill안에 있는지 없는지 O(1)시간으로 확인하기 위해서 set을 만든다

skill_trees를 선회하면서 skill_tree의 각 요소들이 skill 순서에 맞게 나열되어있는지 확인한다.

 

각 skill_tree를 확인할 때마다, skill의 위치를 나타내는 index를 0으로 세팅해준다.

현재 탐색하려는 letter가 skill 안에 있는지를 확인하고 없으면 pass하고 다음 letter~ 있으면 아래의 작업을 수행한다.

letter == skill[index] 일 경우에는 정상상태이므로 index ++ 해주고 pass하고 다음 letter~

letter != skill[index] 일 경우에는 잡았다 요놈.. count-- 해주고 break

 

그리고 index가 skill의 length와 같아지는 경우에는 바로 break해준다.

어차피 우리가 탐색하는 이유는 skill_tree에서 skill 순서에 맞지 않는 요소를 찾기 위해서이므로 skill을 모두 순회한 경우에는 더이상 탐색해줄 필요가 없기 때문이다.

 

... 코드는 매우 더러웠다.

 

코드

import java.util.*;
class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        Set<Character> set = new HashSet<Character>();

        // O(n)
        for(Character letter : skill.toCharArray())
            set.add(letter);

        // O(n^2)   
        int count = 0;
        for(String skill_tree : skill_trees){
            int index = 0;
            count++;
            for(Character letter : skill_tree.toCharArray()){
                if(set.contains(letter)){
                    if(skill.charAt(index) == letter){
                        if(index++ >= skill.length())
                            break;
                    } else{
                        count--;
                        break;
                    }
                }
            }
        }
        return count;
    }
}

 

리뷰 및 수정

역시 세상에 머리 좋은 사람들은 많다...

skill_trees = ArrayList[ skill_tree1, skill_tree2, ... ] 로 가정했을 때

 

정규 표현식을 통해 skil_tree에서 skill이 아닌 요소들을 제거한다.

String skill_elements = skill_tree.replaceAll("[^" + skill + "]", "");

1차 충격.. 난 HashSet을 왜 번거로이 만들어주었던걸까..

 

그리고 indexOf를 통해 한 번에 skill만 통째로 비교해준다.

skill.indexOf(skill_elements) ! = 0

skill.indexOf() == 0의 의미는 skill_elements가 skill의 앞부분부터 맞아떨어진다는거

 

예를 들어

skill = "CBD" 
skill_tree1 = "BACDE"
skill_tree2 = "CBADF"

일 경우

 

정규 표현식 과정을 거치면 각각

skill_tree1 = "BCD"
skill_tree2 = "CBD"

가 된다

 

indexOf를 거치게되면

"CBD".indexOf("BCD") == -1
"CBD".indexOf("CBD") == 0

 

이므로 skill_tree1은 리스트에서 제거된다.

 

 

⁕ 이 밖의 다른 예외상황들도 모두 핸들 가능하다.

 

skill을 모두 완수해야할 필요가 없다.

"CBD".indexOf("CB") == 0
"CBD".indexOf("C") == 0

 

skill 순서는 동일하지만 중간단계부터 시작되는 경우는 배제한다.

"CBD".indexOf("B") == 1
"CBD".indexOf("BD") == 1

 

너무 멋진 코드다... 반했어...❤