[프로그래머스] 스택/큐 - 스킬트리

📌스킬 트리

📕 문제

문제 설명

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

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

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

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

제한 조건

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

입출력 예

skill	skill_trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

입출력 예 설명

• BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• CBADF: 가능한 스킬트리입니다.
• AECB: 가능한 스킬트리입니다.
• BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

---

🥕 나의 풀이

먼저 문제를 이해하는것 조차 힘들었다. 말을 어렵게 써놓은건지.. 내가 못알아듣는건지 모르겠지만.

문제는 skill 매개변수로 들어오는 String과 skill_tress 에 들어오는 String array 를 비교해서 차례대로 들어왔는지 비교하라는게 문제다. Programmer Summer/Winter 2018 문제인데 나는 푸는데 정말 한참 걸렸다. 아직 부족한게 많이 느껴진다.

코드

import java.util.Stack;

class Solution {
    class Data{
        private int findIndex;
        private int skillIndex;

        public Data(int findIndex, int skillIndex) {
            this.findIndex = findIndex;
            this.skillIndex = skillIndex;
        }

        public int getFindIndex() {
            return findIndex;
        }

        public void setFindIndex(int findIndex) {
            this.findIndex = findIndex;
        }

        public int getSkillIndex() {
            return skillIndex;
        }

        public void setSkillIndex(int skillIndex) {
            this.skillIndex = skillIndex;
        }
    }

    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        char[] skill_arr = new char[skill.length()];
        Stack<Data> findIndexStack = new Stack<>();
        Data stackTopVal;
        for(int i = 0 ; i< skill_arr.length ; i ++){
            skill_arr[i] = skill.charAt(i);
        }

        /*
        1. 모두다 못찾아도 ok
        2. 일부 찾았는데, 찾은 순서가 맞으면 ok
        3. 일부 찾았지만 처음 stack에 들어가는게 초기 스킬이 아니면 fail
        */
        for(int i= 0 ; i < skill_trees.length ; i ++){
            for(int j = 0 ; j < skill.length(); j++){
                //찾은 경우
                if(skill_trees[i].indexOf(skill_arr[j]) != -1){
                    findIndexStack.push(new Data(skill_trees[i].indexOf(skill_arr[j]), j)); //찾은 skill index
                }
            }
            if(findIndexStack.isEmpty()) answer++; // 1. 아무런 선행 스킬이 없는 경우

            while (!findIndexStack.isEmpty()){
                stackTopVal = findIndexStack.pop();

                // pop 해서 비어있으면 마지막값이므로 무조건 첫번째 skill index가 와야함
                if(findIndexStack.isEmpty()){
                    if(stackTopVal.getSkillIndex() == 0){
                        answer++;
                        break;
                    }
                }else if((stackTopVal.getFindIndex() < findIndexStack.peek().getFindIndex()) || (stackTopVal.getSkillIndex() - 1 != findIndexStack.peek().getSkillIndex())){ //3. 순서가 맞지 않는 경우
                    break;
                }
            }
            findIndexStack.clear(); // 스택 초기화
        }

        return answer;
    }
}

진짜 진짜 길다. 반성 많이하는중이다. 코딩 테스트들은 문제를 정확하게 이해하는게 먼저라는걸 깨달았다. 다 풀고 다른분의 풀이를 봤는데 정말 많이 배웠다.

---

🥕 다른분의 풀이

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        ArrayList<String> skillTrees = new ArrayList<String>(Arrays.asList(skill_trees));
        //ArrayList<String> skillTrees = new ArrayList<String>();
        Iterator<String> it = skillTrees.iterator();

        while (it.hasNext()) {
            if (skill.indexOf(it.next().replaceAll("[^" + skill + "]", "")) != 0) {
                it.remove();
            }
        }
        answer = skillTrees.size();
        return answer;
    }
}

와우. 코드가 3배넘게 짧다.

위 코드로 배운건 아래와 같다.

1. Array로 들어온거 ArrayList로 받는 방법. Array.asList(array)
2. Iterator를 적극적으로 활용하는 방법
3. 정규식으로 문제를 푼다는 생각
4. 나머지는 잘라버리고 size()로 답을 측정하는 생각

정말 잘하시는분들이 많은 것 같다. 더 열심히 해야겠다.