[200520] 스킬트리 - Summer/Winter Coding(~2018)(level2)

1. 문제이해

- skill(선행 스킬 순서) : 꼭 순서대로 수행해야하는 스킬 순서

- skill_tress(스킬 트리) : 유저가 스킬을 배울 순서

- skill_tress의 원소들 중 skill의 순서를 따라서 가능한 스킬 트리의 개수를 return

 

2. 전략

(1) skillMap 해시맵

- HashMap<String, Integer> : <원소, 순서>

- skill에 포함되는 원소인지 확인할 때 유용하기 때문에 : containsKey(s)

 

(2) skill_trees 확인

- answer : skill_trees의 개수로 초기화

- skillMap.containsKey(s) : skill에 포함되는 원소인지 확인

- current : 현재 확인 중인 skill의 순서(0부터 시작)

- current == skillMap.get(s)라면 current++, 아니라면 answer--

 

3. 참고사항

- contains관련 함수가 있는 자료구조, 컬렉션

- List 컬렉션 : contains()
- Set 컬렉션 : contains()
- Map 컬렉션 : containsKey(), containsValue()

- 다른 풀이 : ArrayList, Iterator 이용

(1) ArrayList
- Arrays.asList(skill_trees)로 ArrayList 초기화
(2) String
- indexOf(요소) : 요소의 index 확인
(3) Iterator
- ArrayList를 iterator로 바꿔서 loop에 이용
- it.next().replaceAll("[^"+ skill + "]", "") : skill에 있는 요소만 남김

**(2)+(3) : if (skill.indexOf(it.next().replaceAll("[^" + skill + "]", "")) != 0)
skill_trees의 해당 요소들이 skill에 포함되는 지 확인하는 코드

 

4. 코드

import java.util.*;
class Solution {
    public int solution(String skill, String[] skill_trees) {
        //hashmap 형성
        String[] temp = skill.split("");
        HashMap<String, Integer> skillMap = new HashMap<>();
        for(int i = 0; i < temp.length; i++){
            skillMap.put(temp[i], i);
        }
        //스킬트리 확인
        int current = 0;
        int answer = skill_trees.length;
        for(String str : skill_trees){
            current = 0;
            String[] s_temp = str.split("");
            for(String s : s_temp){
                if(skillMap.containsKey(s)){
                    if(current == skillMap.get(s)){
                        current++;
                        continue;
                    }
                    else{
                        answer--;
                        break;
                    }
                }
            }
        }
        return answer;
    }
}