[Coding Test] Programmers_Summer&Winter Coding(~2018) 스킬트리

이런 부분은 이렇게 사용했으면 좋겠다! 싶거나 추가했으면 하는 내용은 과감히 댓글 부탁드립니다.

 

[SUMMER&WINTER CODING 스킬트리]

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

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

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

 

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

 

제한 조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.

• 스킬 순서와 스킬트리는 문자열로 표기합니다.

  • 예를 들어, C → B → D 라면 CBD로 표기합니다

• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.

• skill_trees는 길이 1 이상 20 이하인 배열입니다.

• skill_trees의 원소는 스킬을 나타내는 문자열입니다.

  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

 

입출력 예

input:

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

output:

2

 

입출력 예 설명

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

• CBADF: 가능한 스킬트리입니다.

• AECB: 가능한 스킬트리입니다.

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

 

---

문제를 보자마자 생각했습니다. for문과 if문 두 개를 사용하면 되니 comprehension을 이용하면 되겠구나!

그 전에 후딱 테스트를 해보려 작성을 해봤더니 결과는 0

def solution(skill, skill_trees):
    answer = 0
    for i in skill_trees:
        if skill in i:
            answer += 1
    return answer

 

왜그럴까.. if문 안에 hi를 출력하는 코드를 넣어도 역시 반응이없네요.

if skill in i:
    answer += 1
    print("hi")

 

그래서 if문으로 들어가기 전에 i를 출력하면 문자열이 제대로 나오는지를 확인했습니다.

for i in skill_trees:
   print(i)


[output]
BACDE
CBADF
AECB
BDA

제대로 나오네요. 새로운 것을 알 수 있는건가? 타입이 바뀐다면 오류가 떴을테고 계속 고민했습니다.

이번엔 조건문에 직접 문자열을 입력해보았어요.

if "CBD" in i:
    answer+=1

결과는 같았습니다.

 

이 과정에서 한 가지를 깨닫고 망치로 머리를 맞은 것 같았습니다. 아래와 같이 입력을하면 당연히 될 것이라는 느낌이 들더군요.

if "CBD" in "CBDDDDDD":
    answer+=1

입력된 skill_trees의 원소에는 'CBD'가 연속되는 값이 없었기 때문입니다.

ㅋㅋㅋㅋㅋㅋ 이래서 자만하면 안되는 것이죠. 하나를 더 깨달았습니다.

 

그럼 이제 작업 순서는 다음과 같이 작성해야겠다 생각했어요.

1. skill_trees는 반복문을 통해 순서대로 비교함
2. 문자열의 첫 번째(C)를 skill_trees 원소에 비교하고 있으면 패스
3. 그 자리 다음부터 문자열의 두 번째(B)를 skill_trees 원소에 비교하고 있으면 패스
4. ... 그렇게 마지막 문자열까지 비교를 패스하면 answer + 1

이렇게까지 작업이 완료되면 한 가지를 생각할 수 있죠. 문자열 또한 비교를 위해 반복을 해야한다는 것.

 

위 조건을 토대로 작성한 코드입니다.

def solution(skill, skill_trees):
    answer = 0
    
    for tree in skill_trees:
        count = 0
        tmp = 0
        
        for i in skill:
            if i in tree[tmp:]:
                tmp = tree.find(i)
                count += 1
                
        if count == len(skill):
            answer += 1
            
    return answer

결과는 1이 나왔어요. CBD 모두 들어가지 않아도 순서대로이기만 하면 되는 skill_tree 라는 것 간과했습니다.

짧은 시간 동안 다시 자만했던 저를 보며 반성합니다.

 

조건을 추가하고 다시 완성한 코드입니다!

def solution(skill, skill_trees):
    answer = 0

    # skill_trees 원소를 비교하기 위해서 반복문을 사용, 각 유저의 스킬트리(tree)
    # 일치하는 매칭값(mat), 스킬트리에 포함되는 스킬 개수(tot), 비교하는 원소 값을 나누기 위한 기준값(tmp)
    for tree in skill_trees:
        mat = 0; tot = 0; tmp = 0

        # 각 유저들의 스킬트리(tree)를 선행스킬(skill)에 적합한지 비교
        for i in skill:
            tot += tree.count(i)

            # 스킬트리는 선행스킬의 순서대로 진행되어야한다.
            if i == skill[0] or mat >= 1 and mat == skill.find(i):
                if i in tree[tmp:]:
                    tmp = tree.find(i)
                    mat += 1

        # 스킬트리가 선행스킬 조건을 고려했다면 mat과 tot변수가 일치해야 합니다.
        if mat == tot:
                answer += 1

    return answer

 

아래에는 많은 분들이 간결하고 좋다고 공감했던 코드입니다. 한 눈에 봐도 깔끔한 것을 볼 수 있어요.

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer

 

저는 for문을 이용하는 부분에 comprehension을 사용할 수 있을 것 같다고 생각했는데 쉽지가 않았습니다.

혹시라도 포스팅 후에 성공하면 아래 코드로 남겨놓겠습니다!

...

 

HyunJin-Jeong/Practice_Python