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

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

프로그래머스

---

문제를 요약하자면 다음과 같습니다.

주어진 skill의 값이 "CBD" 라면, B를 스킬트리에 넣기 위해선 무조건 선행스킬인 C가 와야하고, D가 오려면 A,B 가 선행스킬로 와야합니다.

 

예시로 보자면 BACDE 같은 경우는 CBD의 순서가 아닌 BCD가 들어갔으므로 올바른 스킬트리가 아니지만 CBADF 같은 경우 CBD 순서로 왔기 때문에 올바른 스킬트리입니다.

 

이 문제를 풀기 위해서 저는 다음과 같은 방법을 생각했습니다.

 

1. 문제에서 주어지는 skill_trees의 요소를 쉽게 만든다.

=> 스킬이 "CBD"이고, skill_trees가 ["BACDE", "CBADF", "AECB", "BDA"] 이렇게 들어오면 CBD의 값만 남겨두었습니다.

즉 skill_trees를 ["BCD", "CBD", "CB", "BD"] 이렇게 되겠죠? 필요 없는 문자를 지워주는 겁니다.

 

2. CBD 순이므로, C = 0, B = 1, D = 2 라는 값으로 두고, skill_trees의 값들을 치환해줍니다.

==> skill_trees는 ["102", "012", "01", "12"] 이렇게 만들어집니다.

 

3. 01 혹은 012 처럼 0부터 순차적으로 올라가는 것에 대해 정답으로 처리해줍니다.

==> 스킬트리 순서이므로 위와 같이 생각했습니다.

---

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = skill_trees.length; // 전체 스킬트리에서 올바르지 않은 스킬트리를 제거하기 위해 다음과 같이 변수 초기화

        List<String> treeList = new ArrayList<>();
        List<Character> skillWord = new ArrayList<>();

        for (int i = 0; i < skill.length(); i++) {
            skillWord.add(skill.charAt(i));
        }

	// 1. skill에 해당하는 문자들만 남겨놓기
        for (String skill_tree : skill_trees) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < skill_tree.length(); i++) {
                if (skillWord.contains(skill_tree.charAt(i))) {
                    sb.append(skill_tree.charAt(i));
                }
            }
            treeList.add(sb.toString());
        }

	// 2. skill 순서에 해당하는 번호로 값 치환하기 ex) "CB" = "01"
        List<String> compareList = new ArrayList<>();
        for (int i = 0; i < treeList.size(); i++) {
            char[] charArr = treeList.get(i).toCharArray();
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < charArr.length; j++) {
                int idx = skill.indexOf(charArr[j]);
                sb.append(String.valueOf(idx));
            }
            compareList.add(sb.toString());
        }


	// 3. 0부터 순차적으로 올라가는 문자가 아니라면 answer -- 를 해서 정답에서 제외 시켜준다.
        for (int i = 0; i < compareList.size(); i++) {
            String str = compareList.get(i);
            for (int j = 0; j < str.length(); j++) {
                if (j != str.charAt(j) - '0') {
                    answer--;
                    break;
                }
            }
        }

        return answer;
    }
}

 

질문 및 피드백은 환영입니다 :)