[파이썬] 백준 9012 : 괄호

[파이썬] 백준 9012 : 괄호

https://www.acmicpc.net/problem/9012

9012번: 괄호

실버 4

자료 구조, 문자열, 스택

---

코드

from collections import deque
import sys

N = int(sys.stdin.readline())
for _ in range(N):
    word = deque(sys.stdin.readline().rstrip())
    dq = deque()
    if word[0] == ')' or word[-1] == '(':
        print('NO')
        continue
    p = word.pop()    # word에서 맨 끝 값을 제거하고, p에 그 값을 바인딩
    dq.append(p)
    while len(word) > 0:
        p = word.pop()
        if len(dq) == 0:
            dq.append(p)
        elif p != dq[-1] and dq[-1] == ')':
            dq.pop()
        else:
            dq.append(p)
    if len(dq) > 0:
        print('NO')
    else:
        print('YES')

 

입력한 문자열에서 괄호가 하나라도 완전히 닫히지 않은 경우 NO를 출력해야 한다.

괄호는 반드시 왼쪽에 '('가, 오른쪽에 ')'가 위치해야 한다.

 

따라서 문장의 맨 처음이 ')'가 오거나 맨 마지막이 '('가 오는 경우는 즉시 NO를 출력하도록 했다.

 

나머지 문장의 경우, 스택 자료구조의 pop과 push의 개념을 응용하여 문자열이 올바른지 확인할 수 있도록 했다.

입력받은 문장을 word라고 할 때, word의 맨 오른쪽에 위치한 데이터를 pop()으로 삭제함과 동시에 새로 선언한 덱에 값을 append()로 삽입했다.

 

word = (())())일 때,
word = (())()
dq = )

 

반복문 속에서 word의 맨 오른쪽 값을 pop()으로 삭제하고, 그 값이 dq에 가장 최근에 추가되었던 값(dq[-1])과 다르다면 dq의 가장 최근의 값 또한 pop()으로 삭제한다. 특히, dp[-1]의 값이 ')'이 되어야 한다. 문자열의 맨 오른쪽에서부터 값을 제거하며 서로 비교하기 때문에 )를 기준으로 (가 word에 존재하는지를 확인하는 것과 같기 때문이다.

만약 두 값이 같다면 word에서 제거된 p를 dq에 append 한다.

 

정리하자면 dq에 존재하는 ) 값과 word의 존재하는 (값을 맨 오른쪽에서 하나씩 제거하는 방법으로 찾아내는 것이다.

word에 존재하는 값이 없으면 반복문을 빠져나온다.

이때 dq에 존재하는 값이 0보다 크면, ()가 짝이 맞지 않았다는 것으로 NO를 출력하도록 한다.

 

word = (())() -> 맨 오른쪽 값 ) 제거
dq = )       -> 가장 최근에 삽입한 값 )
서로 같으므로 dq에 )을 삽입

word = (())( -> 맨 오른쪽 값 ( 제거
dq = ))      -> 가장 최근에 삽입한 값 )
서로 다르므로 dq[-1]을 제거

word = (())  -> 맨 오른쪽 값 ) 제거
dq = )        -> 가장 최근에 삽입한 값 )
서로 같으므로 dq에 )을 삽입

word = (()    -> 맨 오른쪽 값 ) 제거
dq = ))        -> 가장 최근에 삽입한 값 )
서로 같으므로 dq에 )을 삽입

word = ((    -> 맨 오른쪽 값 ( 제거
dq = )))        -> 가장 최근에 삽입한 값 )
서로 다르므로 dq[-1]을 제거

word = (    -> 맨 오른쪽 값 ( 제거
dq = ))        -> 가장 최근에 삽입한 값 )
서로 다르므로 dq[-1]을 제거

word에 아무것도 존재하지 않으므로 반복문 탈출.
dq = ) , len(dq) > 0 이므로 ()의 짝이 맞지 않아 NO를 출력.

 

dq의 값을 제거하는 과정에서 반복문이 끝나지도 않았는데 dq의 값이 텅 비어버리는 경우가 존재한다.

그럴 경우 elif p != dq[-1] and dq[-1] == ')': 에서 인덱스 오류가 나타날 것이다.

 

word = (((()())()일 때, 위와 같은 방법을 사용하면

word의 맨 앞에 ((이 남았을 때 dq에는 값이 남아 있는 게 없어서 dq[-1]값을 구할 수가 없다.

while len(word) > 0:
        p = word.pop()
        if len(dq) == 0:
            dq.append(p)
        elif p != dq[-1] and dq[-1] == ')':
            dq.pop()
        else:
            dq.append(p)

따라서 이와 같은 경우에는 그냥 dq에 p값을 삽입만 하도록 한다.

        if len(dq) == 0:
            dq.append(p) 

dq의 길이가 0이면 값이 없는 것과 마찬가지이므로 p의 값을 삽입만 하도록 한다.