Programmers 문제 - 스킬트리

코딩테스트를 보다가 나온문제인데 코테 볼당시에는 긴장되서 못풀었엇는데, 끝나고 다시한번 풀어보니 풀렸다 ㅋㅋ 왜이렇게 코테볼때만 긴장하는지..

문제

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

하나의 정해진 스킬트리와 여러 스킬트리가 주어지는데, 주어진 스킬트리가 올바른 스킬트리인지 판별하는 문제이다.

풀이

1. Stack을 이용한 풀이

def solution(skill, skill_trees):
    count = []
    for tree in skill_trees:
        answer = True
        # stack을 이용하기 위해 스킬트리를 뒤집고 리스트화
        temp = list(reversed(skill))
        for s in tree:
        	# 주어진 스킬트리가 남아있을 시
            if temp:
            	# 해당되는 순서의스킬을 배울때 다음 스킬로 넘어감
                if temp[-1] == s:
                    temp.pop()
                # 스킬트리의 스킬은 있으나 순서가 아닐때
                elif s in temp and s != temp[-1]:
                    answer = False
                    break
        count.append(answer)

    return sum(count)

주어진 스킬을 뒤집고 리스트화하여 스택을 이용하여 풀이하였다.

2. Queue를 이용한 풀이

from collections import deque

def solution(skill, skill_trees):
    answer = 0
    for tree in skill_trees:
    	# deque를 이용한 queue 생성
        queue = deque(skill)
        
        for sk in tree:
            # 스킬트리의 스킬은 있으나 순서가 아닐때
            if sk in queue:
                if sk != queue.popleft():
                    break
        # inner for 문이 모두 수행되고 아무런 if문에 걸리지 않았을 때
        # else 문 수행
        else:
            answer += 1
    
    return answer

Deque 자료형을 이용하여 queue를 생성하여 풀이한 방법이다. 위의 코드보다 더 간단하고 간결하다.