[프로그래머스 Lv.2] 스킬트리

문제 링크: Lv.2 스킬트리

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

 

need는 필요한 스킬을 순서대로 담고 있는 char[]이고, need[0~need_idx-1]은 이미 배운 스킬을, need[need_idx~]는 아직 배우지 않은 스킬을 가리키고 있다. 다시 말해서, 만약 선행 스킬이 있는 스킬이고 아직 배우지 않은 스킬이라면, 이는 반드시 need[need_idx]와 같아야만 한다. 같을 때에는 잘 배운거니까 need_idx++로써 배움 처리하고 스킬트리의 다음 스킬을 확인하면 되고, 다를 때에는 해당 스킬트리는 '불가능한' 스킬트리이다.

 

Python

def solution(skill, skill_trees):
    answer = 0
    need = [0] * len(skill)
    for i in range(len(skill)):
        need[i] = skill[i]
    
    for skill_tree in skill_trees: # 하나의 스킬트리에 대해서...!
        need_idx = 0
        flag = True
        
        for i in range(len(skill_tree)): # 현재 스킬에 대해서
            currentSkill = skill_tree[i]
            
            # 필요한 스킬이 아니면 무시
            if currentSkill not in need[need_idx:]:
                continue
            
            # 필요한 스킬이 맞으면
            if currentSkill == need[need_idx]:
                need_idx += 1
                continue
                
            # 아직 안 배운 상태면
            else:
                flag = False
                break
                
        if flag:
            answer+=1
            
    return answer

 

Java

class Solution {
    public boolean elemInArr(char target, char[] arr, int start) {
        for (int i = start; i < arr.length; i++)
            if (arr[i] == target)
                return true;
        return false;
    }
    
    public int solution(String skill, String[] skill_trees) {
        /* skill을 한 문자씩 char[] need에 담기 */
        int answer = 0;
        
        char[] need = new char[skill.length()];
        for (int i = 0; i < skill.length(); i++)
            need[i] = skill.charAt(i);
        
        /* 하나의 스킬트리에 대해서 */
        for (String skill_tree : skill_trees) {
            int need_idx = 0; // need[need_idx:]는 안 배운 스킬들
            boolean flag = true; // 지금 스킬트리는 가능한 것인지?
            
            /* 스킬트리의 각 스킬에 대해서 */
            for (int i = 0; i < skill_tree.length(); i++) {
                char currentSkill = skill_tree.charAt(i);
                
                // 지금 스킬은 아직 배우지 않은 스킬인가?
                // YES: in = true, NO: in = false
                boolean in = elemInArr(currentSkill, need, need_idx);
                if (!in) continue; // 배워야 할 스킬 목록에 들어있지 않다면 무시
                
                // 배워야 할 스킬이면, 제일 처음 배워야 할 스킬인가?
                if (currentSkill == need[need_idx]) { // 맞으면
                    need_idx++; // currentSkill을 배운 것으로 처리
                    continue;
                } else { // 아니면(뒤에 배워야 할 스킬인데 유저가 배운다면)
                    flag = false; // 이 스킬트리는 '불가능한' 스킬트리
                    break;
                }
            }
            
            if (flag) answer++; // 이상없이 통과했으면 '가능한' 스킬트리
        }
        
        return answer;
    }
}