프로그래머스 올바른 괄호(lv2, Python)

https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=python3 

프로그래머스

문제 접근

괄호가 문자열로 주어졌을 때 해당 괄호가 올바르게 되어있는지 판별하는 함수를 만드는 문제

 

아이디어

문자열을 하나씩 탐색하는데 여는괄호가 나오면 큐에 저장하고 닫는괄호가 나오면 하나씩 큐에서 제거하는 방식

-> 시간초과

문자열을 하나씩 탐색하는데 여는괄호가 나오면 스택에 저장하고 닫는괄호가 나오면 하나씩 스택에서 제거하는 방식

-> 성공?

 

큐를 활용한 풀이

import queue
def solution(s):
    answer = True
    q = queue.Queue()
    for i in range(len(s)):
        if s[i] == '(':
            q.put(s[i])
        elif s[i] == ')' and q.empty():
            return False
        elif s[i] == ')' and not q.empty():
            q.get()
            
    if not q.empty():
        return False
    
    return True

테스트 케이스는 모두 통과했지만 시간초과로 실패한 모습...어떻게 최적화할 수 있을까?

 

스택을 활용한 풀이

def solution(s):
    stack = []
    for i in s:
        if i == '(':
            stack.append(i)
        else: # 닫는 괄호가 나올 경우
            if stack == []: #스택이 비어있는데 닫는 괄호가 나오는 경우
                return False
            else:
                stack.pop()
    return stack == [] #스택이 비어있으면 true