Gidhub BE Developer

[Programmers] 스킬트리

2021-01-17
goodGid
Algorithm

스킬트리

Problem

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

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

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

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

[1] Code (21. 01. 17)

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));
        Iterator<String> it = skillTrees.iterator();

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

  • Regex 사용한 풀이다.

  • skill_trees에 있는 n 번째 String에서

    skill에 없는 값을 “” 공백 처리 후

    그 값을 skill에서 indexOf( )로 찾는다.

  • 그리고 그 indexOf( ) 값이 0이 아니라면

    skill의 순서가 어긋난 걸로 볼 수 있다.

Regex : ^skill

^ : 부정을 뜻한다.
[] : [abc]라면 a,b,c라는 값이 독립적으로 존재하는지 찾는다.
  • 즉 [^CBD]라면 C,B,D가 아닌 문자를 찾게 된다.

[2] Code (21. 01. 17)

import java.util.*;

class Solution {
 public int solution(String skill, String[] skill_trees) {
        int answer = 0;

        HashSet<Character> set = new LinkedHashSet<>();
        for (char c : skill.toCharArray()) {
            set.add(c);
        }

        for (String s : skill_trees) {
            if (solve(set, s)) {
                answer++;
            }
        }
        return answer;
    }

    private boolean solve(HashSet<Character> set, String s) {

        char[] chars = s.toCharArray();
        Object[] skill = set.toArray();

        int idx = 0;

        for (char c : chars) {
            if (idx == skill.length) {
                return true;
            }

            if (skill[idx].equals(c)) {
                idx++;
                continue;
            } else if (set.contains(c)) {
                return false;
            }
        }
        return true;

    }
}

  • 중복이 없다 라는 조건을 보고 Set 혹은 Map을 떠올렸다.

    그런데 굳이 K/V 구조가 필요 없으므로 Set 자료구조를 사용하였다.

skill       : "CBD"	
skill_trees : ["BACDE", "CBADF", "AECB", "BDA"]
  • 예제를 통해 코드를 이해해보자.

Case 1

초기에 idx 필드는 skill의 'C' 값을 가리킨다.
"BACDE"는 B->A->C->D->E 순서로 비교한다.

skill[idx]와 "B"는 다르다.
그런데 Set 자료구조에 B 값이 존재한다.
= B가 C보다 먼저 나올 순 없다.
= 문제 조건 충족 X

Case 2

초기에 idx 필드는 skill의 'C' 값을 가리킨다.
"CBADF"는 C->B->A->D->F 순서로 비교한다.

skill[idx]와 "C"는 같다.
그러면 idx 값을 증가시킨다.

skill[idx]와 "B"는 같다.
그러면 idx 값을 증가시킨다.

skill[idx]와 "A"와 다르다.
그렇지만 Set 자료구조에 A는 없다.
무시하고 넘어간다.

skill[idx]와 "D"는 같다.
그러면 idx 값을 증가시킨다.

idx의 크기는 skill.length와 같으므로
문제 조건을 충족시켰다고 판단한다.

Case 3

초기에 idx 필드는 skill의 'C' 값을 가리킨다.
"AECB"는 A->E->C->B 순서로 비교한다.

skill[idx]와 "A"와 다르다.
그렇지만 Set 자료구조에 A는 없다.
무시하고 넘어간다.

skill[idx]와 "E"와 다르다.
그렇지만 Set 자료구조에 A는 없다.
무시하고 넘어간다.

skill[idx]와 "C"는 같다.
그러면 idx 값을 증가시킨다.

skill[idx]와 "B"는 같다.
그러면 idx 값을 증가시킨다.

"AEBC" 값을 다 읽었으므로
문제 조건을 충족시켰다고 판단한다.

Summary

  • Regex로 접근하는 풀이는 신선했다.

    skill에 해당하는 값을 찾는 게 아니라

    해당하지 않는 값을 제거 후 비교한다.

    아주 좋은 아이디어를 배웠다.

Reference

Recommend

Index