본문 바로가기
알고리즘

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

by minkang 2021. 1. 21.

programmers.co.kr/learn/courses/30/lessons/49993

 

코딩테스트 연습 - 스킬트리

 

programmers.co.kr

import java.util.HashMap;
class Solution {
    public int solution(String skill, String[] skill_trees) {
    	HashMap<Character, Integer> hs = new HashMap<Character, Integer>();
    	for(int i=0; i<skill.length(); i++) {
    		hs.put(skill.charAt(i), i);
    	}
        int answer = 0;
        outer: for(int i=0; i<skill_trees.length; i++) {
        	int idx = 0;
        	for(int j=0; j<skill_trees[i].length(); j++) {
        		if(hs.containsKey(skill_trees[i].charAt(j))) {
        			if(idx != hs.get(skill_trees[i].charAt(j))) {
        				continue outer;
        			}
        			idx++;
        		}
        	}
        	answer++;
        }
        
        return answer;
    }
}

소요시간 : 15분

어떤 스킬을 찍으려면 선행으로 찍어야 되는 스킬이 있다.

선행스킬트리를 skill String에 받고 다양한 스킬트리에 대해서 적용이 되는지 테스트 하는 문제이다.

선행스킬이 "ABC"가 있다면 hashMap에 {A, 0}, {B, 1}, {C, 2} 이런 식으로 저장하고

스킬트리가 "DBACE"라면 idx를 0으로 시작하여 각각의 문자값이 해쉬에 있는지 비교한다.

이 때 B를 만났을때 idx는 0 즉, A를 안 찍은 상태이므로 적용할 수 없는 스킬트리이다.