[Programmers/Python] 올바른 괄호 || Stack & Queue

프로그래머스

프로그래머스 파이썬 올바른 괄호 12909

문제 설명 )

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항 )

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

 

📌 문제 풀이

스택이나 큐를 이용하여 문제를 쉽게 해결할 수 있다!
입력된 문자열을 하나씩 for문을 돌면서
1. "("인 경우, push
2. ")"인 경우, pop
만약 스택이나 큐가 비워져있어서 pop이 불가능하다면, False
for문이 모두 돌고 나서 스택이나 큐에 원소가 남아있는 경우도 False이다.
 

✅ [ CODE ]

def solution(s):
    stack = []
    for i in s:
        if i == "(":
            stack.append("(")
        else:
            if len(stack) != 0:
                stack.pop()
            else:
                return False
    
    if len(stack) != 0:
        return False
    else:
        return True

stack이라는 리스트를 활용하여 스택에 push & pop을 이용한 풀이이다.
 

✅ [ CODE ]

from collections import deque

def solution(s):
    queue = deque()
    for i in s:
        if i == "(":
            queue.append("(")
        else:
            if len(queue) != 0:
                queue.pop()
            else:
                return False
    if len(queue) != 0:
        return False
    else:
        return True

파이썬에서의 deque는 popleft / pop - appendleft / append로 메서드를 활용할 수 있어 스택이나 큐에서도 쉽게 활용이 가능하다. 
위에서의 코드는 자료구조 큐를 이용한 풀이이다.
첫 번째 코드도 deque를 활용하여 스택으로 풀이가 가능하다.