문제링크

문제 이해

[ 입력형태 / 조건 ]

skill
각 스킬은 알파벳 대문자로, 선행 스킬 순서를 나타낸 문자열 | "CBD"

skill_trees
판별해야할 스킬순서 | ["BACDE", "CBADF", "AECB", "BDA"]

[ 문제 ]

=> 선행 스킬 순서를 만족하는 개수를 return

[ 풀이 ]

Map에 알파벳:순서 형태로 저장하고, 각 주어진 스킬 순서들을 순회하며 알맞은 순서인지 점검

---

코드

> [성공] 1차 시도 : Map 이용

• 생각한 풀이 그대로 구현

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = skill_trees.length;
        Map<Character, Integer> map = new HashMap<>();
        for(int i=0; i<skill.length(); i++){
            map.put(skill.charAt(i), i+1);
        }
        
        for(String cs : skill_trees){
            int order = 0;
            for(int i=0; i<cs.length(); i++){
                char cur = cs.charAt(i);
                if(map.containsKey(cur)){
                    if(order + 1 == map.get(cur)){
                        order+=1;
                    }else{
                        answer-=1;
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

=> 괜찮은 결과가 나왔음

> [성공] 2차 시도 : 배열 이용

• 알파벳은 26개 이므로 배열로 구현해도 될것이라 생각

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = skill_trees.length;
        
        int[] alpha_order = new int[26];
        for(int i=0; i<skill.length(); i++){
            alpha_order[skill.charAt(i) - 'A'] = i+1;
        }
        
        for(String cs : skill_trees){
            int order = 0;
            for(int i=0; i<cs.length(); i++){
                int val = alpha_order[cs.charAt(i) - 'A'];
                if(val != 0){
                    if(order + 1 == val){
                        order+=1;
                    }else{
                        answer-=1;
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

=>Map보다 빠르게 실행이 가능했음
Map의 contains연산보다 단순 어레이 인덱싱이 빠르기 때문!

TIP : contains연산을 자주 써야 한다면 배열로 저장하는 것이 좋고, 비연속적인 극과 극의 값이 이산적인데 많지 않으면 Map을 사용하는 것이 좋다