괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 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를 활용하여 스택으로 풀이가 가능하다.
