[python] 프로그래머스 스킬트리

 

programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리

윈터코딩 ~2018 에 속한 문제.

시간복잡도 고려

최대 가능한 연산수가 26*26*20이기에 O(n^2) 까지의 시간복잡도여도 문제가 없을 것으로 예상된다.

 

코드

from collections import deque
from copy import deepcopy
def solution(skill, skill_trees):
    answer = 0
    p_skill = deque([])
    for c in skill:
        p_skill.append(c)
    for skill in skill_trees:
        if check(p_skill,skill):
            answer +=1
    
    return answer

def check(skill_way,tree):
    skill_copy = deepcopy(skill_way)
    for c in tree:
        if not skill_copy:
            return True
        first = skill_copy.popleft()
        if first == c:
            continue
        elif c in skill_copy:
            return False
        else:
            skill_copy.appendleft(first)
    return True

 

스킬의 선행 순서를 p_skill 에 저장 후, 스킬트리 리스트의 각 스킬트리 별로 check 함수를 호출해 정상적인 스킬트리인지의 여부를 판단한다.

 

deep_copy 를 통해 원본 큐에 영향이 없는 복사본을 만들고, 이 큐의 맨앞 원소와 비교한다.

1. 맨앞 원소 first 와 현재 스킬 c 가 같을 경우

정상이다.

2. first 와 같지 않지만 후속되는 스킬들인 경우

선행되는 스킬인 first 를 찍지않았으므로 불가능한 경우이다. 비정상

3. 선행스킬트리에 없는 스킬인 경우

문제없다. 정상

 

큐를 활용했기때문에 리스트에서 pop(0) 을 하는 경우에 비해 시간복잡도가 O(n) -> O(1) 로 줄어든다.

 

근데 인풋 크기 자체가 크지않아서 고려하지 않아도 통과 가능하다.