[프로그래머스] 스킬트리 (Level 2, Python)

 

 

온라인에서 코딩테스트 문제를 풀 수 있는 프로그래머스의 Level2 스킬트리 문제.

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

 

문제 설명

 

해당 문제는 선행 스킬 순서가 담긴 skill 배열과 유저들이 만든 스킬트리가 담긴 배열 skill_trees가 매개변수로 주어진다. 그리고 가능한 스킬트리 개수를 return하는 문제이다.

 

문제를 간단히 살펴보면 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻한다. 그리고 선행 스킬이 존재하지 않는 스킬은 언제든지 배울 수 있다.

 

예를 들어 "League Of Legend"에서 레벨이 아닌 선행 스킬에 따라 스킬을 배울 수 있다면 어떨까? "누누"라는 챔피언이 데굴데굴 눈덩이!(W)를 배우기 위해서는 잡아먹기(Q)를 먼저 배워야 한다고 가정해보자. 잡아먹기를 배우기 전까지는 데굴데굴 눈덩이를 사용할 수 없을 것이다. 그리고 눈덩이 팡팡팡(E)은 선행 스킬이 존재하지 않는다고 가정하면 어떠한 선행 스킬 없이도 언제든지 사용할 수 있을 것이다.

 

문제로 돌아오자.

 

테스트 케이스로 주어진 skill 배열에는 ["CBD"]라는 선행 스킬의 순서가 담겨있다. 그리고 skill_trees 배열에는 유저들이 만든 스킬트리 ["BACDE", "CBADF", "AECB", "BDA"]가 담겨있다. 

 

"BACDE"를 먼저 살펴보면 A와 E는 선행 스킬이 존재하지 않기 때문에 언제든지 배워도 상관이 없다. 하지만 "BCD"는 선행 스킬이 존재하는 스킬트리이다.

 

첫 번째 요소인 B는 C를 먼저 배워야 사용할 수 있는 스킬이다. 따라서 C보다 B를 먼저 찍는 챔피언은 존재할 수 없기 때문에 유효한 스킬트리가 아니다. 반면에 두번째 요소인 "CBADF"를 살펴보면 A와 F는 선행 스킬이 존재하지 않기 때문에 언제든지 배울 수 있고, 나머지 스킬인 C-B-(A)-D-(F)를 순서대로 배우고 있기 때문에 유효한 스킬트리이다.

 

따라서 주어진 skill_trees의 모든 요소를 확인하면 유효한 스킬트리는 2개이기 때문에 결과값은 2가 된다.

 

코드 설명

 

작성한 코드는 다음과 같다. (python3)

 

def solution(skill, skill_trees):

  answer = 0

  for i in skill_trees:
    list = []
    fin = True
    
    for j in range(len(i)):
      if i[j] in skill:
      	list.append(i[j])

    for k in range(len(list)):
      if list[k] != skill[k]:
        fin = False
        break

  if fin == True:
  	answer += 1

  return answer

 

코드의 컨셉은 다음과 같다.

 

1. 첫번째 루프에서 skill_trees에 담긴 요소를 하나씩 꺼내고, 선행 스킬이 필요한 스킬만을 담을 list 배열과 유효하지 않은 스킬트리를 체크하기 위한 fin을 True로 초기화한다.
2. 두번째 루프에서 i[j]를 선행 스킬의 순서가 담겨있는 skill 배열과 비교하여 선행 스킬이 필요한 스킬만을 list 배열에 담는다.
3. 생성한 list 배열의 길이 만큼 skill 배열과 같은 인덱스로 비교하여 값이 일치하지 않을 경우 fin을 False로 변경한다.
4. fin이 True일 경우 유효한 스킬 트리이기 때문에 answer의 값에 1을 더해준 후 다시 루프를 반복한다.

해당 코드에서의 핵심은 선행 스킬이 필요한 스킬만을 담은 list 배열의 길이만큼 skill 배열과 비교하는 부분이다.

 

예를 들어 선행 스킬이 A-B-C의 순서라면 A를 먼저 배우지 않고서는 B와 C 스킬을 배울 수 없기 때문에 유효한 스킬트리라면 list 배열의 길이만큼 skill 배열과 같은 인덱스에서 같은 값을 가져야 하기 때문이다.

---

 

 

안녕하세요. 평범한 대학생 개발자 yorr입니다.

포스팅을 읽고 궁금한 점 또는 문의가 있으신 분은 메일 또는 댓글을 남겨주세요.

 

Mail: twysg@likelion.org

Github: https://github.com/sangyeol-kim