각각의 테스트 케이스는 독립적
테스트 케이스 하나에 대해 어떻게 해결하면 되는지 알아내면 되는 문제
올바른 괄호쌍을 구하는 문제 : 전형적인 Stack
을 사용하는 문제
ex) ((()))
위의 경우 세 쌍의 괄호가 있음
차례로 여는 괄호를 1, 2, 3이라고 칭한다면, 닫는 괄호는 4, 5, 6
→ 쌍 : (1,6), (2,5), (3,4)
→ 여는 괄호가 들어오는 순서와 닫는 괄호가 들어오는 순서는 역순
현재 스택 상태(Bottom to Top) : 1 2 [3 4] → pop
현재 스택 상태(Bottom to Top) : 1 [2 5] → pop
현재 스택 상태(Bottom to Top) : [1 6] → pop
stack.append()
or stack.pop()
결정(
일 경우 : VPS가 되기 위해 )
가 들어와야 pop될 수 있으므로 stack.append()
)
일 경우 : VPS의 조건을 만족하므로 )
를 append
할 필요 없이 쌍이 되는 (
를 stack.pop()
# step 1
T = int(input())
for _ in range(T):
stack = [] # list로 Stack 구현
for char in input():
# 여는 괄호의 경우 stack에 append
if char == '(':
stack.append(char)
# 닫는 괄호의 경우 stack에 있는 여는 괄호와 한 쌍이 이루어지므로 pop
else:
stack.pop()
만약 step1에서 입력된 문자열이 ((()))
와 같을 경우, 마지막 닫는 괄호가 pop되면 모든 조건을 완료함
→ ((())))()
과 같이 6번째 문자(세번째 닫는 괄호)에 stack의 모든 문자가 Pop되고, stack은 비어있는 상태가 됨
→ 이 때 7번째로 들어오는 )
의 경우 ? 비어있는 stack에서 stack.pop()
명령어가 수행되므로 오류 발생
# step 2
T = int(input)
for _ in range(T):
stack = [] # list로 Stack 구현
for char in input():
# 여는 괄호의 경우 stack에 append
if char == '(':
stack.append(char)
# 닫는 괄호의 경우
else:
# stack - !empty : stack에 있는 여는 괄호와 한 쌍이 이루어지므로 pop
if len(stack) > 0:
stack.pop()
# stack - empty : stack이 비어있으므로 break
else:
break
step2까지의 과정을 통해 모든 입력값에 대해 오류 없이 stack 작업을 수행할 수 있게 됨
→ 남은 작업 : 입력된 행이 VPS 조건을 만족할 경우 YES
, 만족하지 못할 경우 NO
출력
isVPS
를 선언해 분기에 따라 플래그 업데이트# step 3
T = int(input())
for _ in range(T):
# i가 특별히 할 일이 없을 경우 _로 대체 가능
stack = [] # list로 스택 구현
isVPS = True
for char in input(): # 한줄씩 입력받아 문자 하나씩 순회
if char == '(':
stack.append(char)
else:
# if stack == if len(stack) > 0
if len(stack) > 0:
# ((()))와 같이 여는 괄호와 닫는 괄호가 함께 들어온 경우, 즉 스택이 비게 되는 경우
stack.pop() # 닫는 괄호가 들어왔기에 여는 괄호를 pop
else:
isVPS = False
break
if stack:
isVPS = False
print('YES' if isVPS else 'NO')
()()()
처리는 쉬울 것 같아 보였으나, 오히려 ((()))
의 입력값 처리에 대해 막히게 되었다.()()()
가 쉬울 것 같아 보였던 이유는 배열을 본 문제의 자료구조로 활용하려 하였기 때문. depth가 커지는 것에 대해 인덱스로 접근하는 방법에서 막혔다고 판단된다. 이전에 작성했던 코드를 다시 제출했을 때 오답 처리가 되었다.
그래서 다시 풀이한 코드를 첨부한다!
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
stack = []
isVPS = True
for char in input():
if char == '(':
stack.append(char)
if char == ')':
if stack:
stack.pop()
elif not stack:
isVPS = False
break
if not stack and isVPS:
print('YES')
elif stack or not isVPS:
print('NO')