깃허브:
https://github.com/MSIQOC/Programmers/blob/main/%EC%98%AC%EB%B0%94%EB%A5%B8%EA%B4%84%ED%98%B8.py
https://programmers.co.kr/learn/courses/30/lessons/12909?language=python3
코딩테스트 연습 - 올바른 괄호
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은
programmers.co.kr
올바른 괄호 문제는 스택을 활용하는 문제이고 왼쪽 괄호가 나오면 스택에 추가해주고 오른쪽 괄호가 나오면 스택에서 pop을 해주는 식으로 풀면 된다.
다음 몇가지 경우의 수들만 기억하면 쉽게 풀 수 있다.
1. 오른쪽 괄호부터 시작하는 경우 (False)
2. 순회가 다 끝났는데 스택에 왼쪽 괄호가 남아있는경우 (False)
3. 모든 괄호가 짝이 다 맞아서 마지막에 스택이 비게 된 경우 (True)
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def solution(s):
stack = []
for i in s:
if i == '(':
stack.append(i)
else:
if stack == []: # 오른쪽 괄호로 시작할경우
return False
else:
stack.pop()
if stack != []: # 다 끝났는데 왼쪽 괄호가 스택에 남아있을경우
return False
return True
|
cs |