[알고리즘 문제 풀이] - 스킬 트리 (프로그래머스)

 

매일 최소 한 문제씩 코딩테스트 준비겸 알고리즘 문제를 풀고 있습니다.

 

오늘은 프로그래머스에서 스킬트리를 풀어봤습니다. 

 

<문제 설명>

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

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

 

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

 

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

<제한 사항>

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 CBD로 표기합니다.

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

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

앞의 스킬을 배워야 뒤의 스킬을 배울수 있다는점이 문제의 키 포인트 같습니다.

 

리스트 안에 있는 각 스킬트리들의 스킬이 선행 순서에 맞는지 확인하는 작업이 필요해 보이네요.

 

그래서 저는 스킬 트리 안에서 선행 스킬이 필요한 스킬을 찾을때마다

 

이 스킬이 지금 배울수 있는 스킬인지 아니면 앞에 다른 스킬을 배워야 가능한 스킬인지를

 

if-statement를 이용해서 확인하고

 

선행 스킬순서에 어긋나는 경우를 발견했을때

 

시간을 절약하기 위해 break 하도록 하였습니다.

 

def solution(skill, skill_trees):
    answer = 0	#가능한 스킬트리의 수
    
    for tree in skill_trees:
        stack = [x for x in skill]	#선행 스킬순서를 리스트에 담는다
        stack.reverse()
        
        for ch in tree:	
            if ch in stack and ch != stack[-1]:	#순서에 맞지 않은 스킬트리 
                break
            if ch in stack and ch == stack[-1]: #순서에 맞는 트리
                stack.pop()
        else:
            answer += 1		#가능한 스킬트리를 발견
            
    return answer

파이썬에는 for-else 문이 있다는게 정말 다행이네요.

 

break로 for loop이 중간에 종료 되는 일 없이 끝까지 돌아갔을 경우 else 문으로 빠집니다. 

 

 

 

 

즉, 선행 스킬 순서에 어긋나지 않는 가능한 스킬 트리는 else로 반드시 빠진다는 뜻이죠.

 

여기서 reverse()를 써서 선행 스킬의 순서를 뒤집어 놓았는데요.

 

그 이유는 스킬을 순서대로 배워나갈때마다 stack안에서 하나씩 pop을 하는데

 

pop(-1)은 시간 복잡도가 O(1)이고 pop(0)는 O(N)이기 때문에

 

시간을 줄이기 위해서 였습니다.

 

즉, reverse()로 인해서 선행 스킬의 첫번째 스킬은 마지막 자리로 이동이 되었습니다.

 

항상 되도록이면 속도를 최대한 빠르게 하는 방향으로 코드를 짜고 있는데요

 

이정도 결과면 만족스럽네요 ㅎㅎ