프로그래머스 - 스킬트리

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

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

1. 접근법

 

해시맵

 

2. 로직

1) skill에 대한 <알파벳, 인덱스 번호> 딕셔너리 생성

2) skill_trees중 skill이 포함된 경우, 인덱스를 기준으로 그 전 스킬들을 찍었는지 확인

 

 

다른 풀이

sas-study.tistory.com/342

[Java 알고리즘] 프로그래머스, 스킬트리

이 분은 자료구조를 사용하지 않고 replace와 indexOf를 사용해서 풀었습니다.

 

 

3. 코드

import java.util.*;
class Solution {
    static HashMap<Character, Integer> dic;
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        dic = new HashMap<>();
        char skillChar[]=skill.toCharArray();
        int pos=0;
        for(char ch:skillChar){
            dic.put(ch, pos++);
        }
        for(String skill_tree:skill_trees){
            skillChar = skill_tree.toCharArray();
            boolean visit[] = new boolean[skill.length()];
            boolean flag = true;
            for(char ch:skillChar){
                if(dic.containsKey(ch)){
                    int idx= dic.get(ch);
                    if(!skillCheck(skill, idx, visit)){
                        flag= false;
                        break;
                    }
                }
            }
            if(flag){
                answer++;
            }
        }
        return answer;
    }
    static boolean skillCheck(String skill, int idx, boolean []visit){
        char c[] = skill.toCharArray();
        visit[idx] = true;
        for(int i=0; i<idx; i++){
            if(!visit[i])
                return false;
        }
        return true;
    }
}