세무민의 코딩일기 : 프로그래머스 스킬트리 문제 풀기

확실한 건 그리디랑 동적 다이나믹 프로그래밍 공부를 안하다보니 멘탈은 괜찮아지구

쉬운 문제들만 풀어서 그런가... 오늘 4문제나 풀었다 ㅋㅋㅋㅋㅋㅋㅋㅋ

그 중 한문제를 소개해보면!

바로 스킬트리 문제!

이 문제는 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 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

[ 입출력 예 ]

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

[ 입출력 예 설명 ]

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

 

---

풀이

이 문제에 포인트는 아스키코드를 이용하는 것과 Skill에서 주어진 스킬을 제외한 스킬들은 의미가 없는것!

예를 들어서 

Skill = "ADC" 라고 가정했을 때

Skil_Tree1 = AERWDZZXC

위에 Skill_Tree1은 Skill과 일치하기 때문에 가능한 값이 된다.

Skill_Tree2 = "DERWAZZFKC

Skill_Tree2는 가능할까? 불가능하다.

그 이유는 Skil의 순서에 일치하지 않기 때문이다. 

결론적으로는 Skill 순서에 알맞게 값이 들어가면 된다는 점이다.

요약하면

1. Skill에 순서에 일치한지 확인

2. CheckList를 만들어서 Skill에 일치하는 값만 체크하기

---

코드

def solution(skil, skill_trees):
    skilCount = [0] * 26

    count = 0
    for i in range(len(skil)):
        tmp = ord(skil[i]) - ord("A")
        skilCount[tmp] = i + 1


    for i in skill_trees:
        result = ""
        for j in range(len(i)):
            tmp2 = ord(i[j]) - ord("A")
            if skilCount[tmp2] != 0:
                result += i[j]


        if result in skil[:len(result)]:
            count += 1

    return count

나는 위의 코드처럼 문제를 풀었다. 

SkillCount는 알파벳 A부터 Z까지인 26개의 크기만큼 0으로 셋팅해준다.

그 후 Skill에 값을 아스키코드로 변환 후 아스키코드 A를 뺀 값을 리스트에 체크한다. 

해당 스킬트리를 2중포문으로 SkillCount에 존재하는 값이 있다면 result로 추가한 후 

result값이 skil에 존재하는지 확인해주면 끝!

그리고 확인 된 수만큼 출력해주면 됩니다.

끝!

---

토요일에 시험인데... 아직도 다이나믹프로그래밍하고 탐색부분을 공부못했지만..

꾸준히 공부하다보면 언젠간 기회가 올 것이라고 생각한다.

무튼 다음에도 더 좋은 포스팅으로 찾아오겠습니다.