[알고리즘 / 프로그래머스] 스킬 트리

 

문제는 위와 같으며 skill 의 문자를 하나씩 skill_trees 의 요소에서 찾아서 그 인덱스를 저장하고 순서가 더 뒤에 있지만 앞 인덱스보다 먼저 찾은 경우 순서를 틀린 것으로 하여 반복을 종료하고 그렇지 않고 끝까지 인덱스의 오름차순을 지킨 경우 가능한 스킬트리 개수를 하나 증가하는 방식으로 문제를 해결하였습니다.

 

파이썬 코드는 다음과 같습니다.

# 코딩테스트 연습 > Summer/Winter Coding(~2018) > 스킬트리

skill = "CBD"
skill_trees = ["BACDE", "CBADF", "AECB", "BDA"]

answer = 0

for sk in skill_trees:
    i = -1
    count = 0
    for s in skill:
        idx = sk.find(s)
        if idx == -1:
            idx = len(sk)

        # 지금까지 익힌 스킬의 인덱스보다 현재 스킬의 인덱스가 더 먼저인 경우 종료
        if i > idx:
            break

        i = idx
        count += 1

    # skill 을 모두 검사할 동안 오름차순이 유지된 경우
    if count == len(skill):
        answer += 1

print(answer)

 

자바 코드는 다음과 같습니다.

public class SkillTrees {
    public static void main(String[] args) {
        String skill = "CBD";
        String[] skill_trees = {"BACDE", "CBADF", "AECB", "BDA"};

        int answer = 0;

        for (String sk : skill_trees) {
            int idx = -1;
            int count = 0;

            for (int i = 0; i < skill.length(); i++) {
                int f = sk.indexOf(skill.charAt(i));
                if (f == -1) {
                    f = sk.length();
                }

                if (idx > f) {
                    break;
                }

                idx = f;
                count++;
            }

            if (count == skill.length()) {
                answer++;
            }
        }

        System.out.println(answer);
    }
}

 

위 코드에서 입출력을 제외한 부분을 프로그래머스 Solution 함수에 넣으면 문제를 통과할 수 있습니다.