프로그래머스 스킬트리 Summer / Winter Coding 2018

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

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

 

안녕하세요 !

오늘은 프로그래머스 스킬트리 문제를 풀어봤습니다

이 문제는 어제 푼 메뉴 리뉴얼 문제보다 비교적 쉬운 문제였습니다!!

 

• 스킬트리

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한 조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 "CBD"로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예skillskill_treesreturn

"CBD"

["BACDE", "CBADF", "AECB", "BDA"]

2

 

---

저는 

먼저 skill 문자열의 문자를 ArrayList 에 넣은 다음 

 

skill_tree 배열의 문자열을 반복하면서

 

각 문자가 ArrayList에 있는 문자인지 확인합니다

만약 문자열에 있는경우 

첫번째는 ArrayList에 0번째 인덱스여야하고

두번째는 1번째 인덱스 

인지 확인하는 과정을 거치고 만약 다를 경우 answer 에 1을 더하지 않습니다!

만약 첫번째로 발견된 것이 C가 아닌 B 일 경우 불가능한 스킬트리입니다!

import java.util.ArrayList;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        ArrayList<Character> list = new ArrayList<>();
        char [] chars = skill.toCharArray();
        for(int i = 0 ; i<chars.length; i++){
            list.add(chars[i]);
        }
        for(int  i = 0 ; i<skill_trees.length ; i++){
            char [] charArray = skill_trees[i].toCharArray();
            int index = 0;
            boolean check = true;
            for(int j =0 ; j<charArray.length; j++){
                if(list.contains(charArray[j])){
                    if(list.indexOf(charArray[j])==index){
                        index++;
                    }else{
                        check = false;
                        break;
                    }
                }
            }
            if(check){
                answer++;
            }
        }
        return answer;
    }

    public static void main(String [] args){
        System.out.println(
                new Solution().solution("CBD",new String[]{"BACDE","CBADF","AECB","BDA"})
        );
    }
}