[Programmers] 스킬트리 (JAVA)

프로그래머스

 

풀이

 

스킬을 배워야하는 순서가 C => B => D 라면,

C만 배우기	가능	C => B	가능	C => B => D	가능
B만 배우기	불가능	D만 배우기	불가능	B => D	불가능

 

당연히 D를 먼저 배우고 C를 배우는 경우도 불가능하다.

대신 skill에 없는 다른 스킬들은 언제든 배울 수 있음.

 

그럼 가능한 경우를 숫자로 바꿔 HashMap을 사용해 map2에 넣어두고,

skill_trees 배열에 있는 스킬트리들이 가능한지 체크해준 다음

map2에 있으면 배울 수 있는 스킬트리이기 때문에 ans++해줬다.

 

전체코드

import java.io.*;
import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        HashMap<String, Integer> map = new HashMap<>();
        HashMap<String, Integer> map2 = new HashMap<>();
        
        int answer = 0;
        String check = "";
        String tmp = "";
        for(int i=0; i<skill.length(); i++){
            map.put(skill.charAt(i)+"", i+1);
            tmp += (i+1);
            map2.put(tmp, 1);
        }
        
        char skilltrees[] = skill.toCharArray();
        
        for(int i=0; i<skill_trees.length; i++){
            check = "";
            for(int j=0; j<skill_trees[i].length(); j++){
                if(map.containsKey(skill_trees[i].charAt(j)+"")){
                    check += (map.get(skill_trees[i].charAt(j)+""));
                }else{
                    continue;
                }
            }
            
            if(check.length() == 0){
                answer++;
            }else{
                if(map2.containsKey(check)){
                    answer++;
                }else{
                    continue;
                }
            }
        }
        
        return answer;
    }
}