[코테] 큐 - 스킬트리[프로그래머스]

문제

출처: 프로그래머스 - 스킬트리

풀이:

skill_trees를 반복문으로 순회하면서 스킬트리를 하나씩 꺼내와서 skill과 비교한다.
비교할 때는 deque를 사용하여 큐 자료구조를 만들어 제일 앞의 문자를 비교한다. 리스트는 순서가 있는 배열이기에 제일 앞의 것을 빼내게 되면 재정렬을 하는 연산을 하기에 상수 O(1)의 연산을 하는 deque를 사용하는 것이 좋다. 문제 제시에서는 길이가 짧지만 문자열이 길다면 시간 초과에 걸릴 수도 있다.

순서를 지켜야 하기에 스킬트리의 앞부분과 skill의 앞부분을 비교하는데, 스킬트리에는 다른 스킬들이 있어도 되지만 순서는 skill의 순서를 지켜야하며, skill의 모든 스킬이 스킬트리에 있어야 하는 것은 아니다.

'for~else'를 사용하여 연산 횟수를 더 줄인다. 'for~else'문은 for문이 break를 만나지 않고 정상적으로 반복문이 작동했다면 else문으로 가서 연산을 진행한다. 만약 for 반복문이 진행하는 동안 break를 만나게 되면 else문은 작동하지 않는다. 그래서 for문이 끝나고 다음에 다른 연산을 진행할 필요가 없어 연산 횟수를 줄일 수 있다.

코드

from collections import deque
def solution(skill, skill_trees):
    answer = 0
    for tree in skill_trees: # 스킬트리를 하나씩 꺼내와서 비교해 본다.
        dQ = deque(tree)
        sQ = deque(skill)
        
        for _ in tree: # 스킬트리의 길이만큼 반복.
            x = dQ.popleft()
            if x in skill:
                if x != sQ.popleft():
                    break
        else: # for 반복문이 정상적으로 끝났다는 말은 스킬트리가 skill의 순서를 지켰다는 의미.
            answer += 1

    return answer