[9012] 괄호

 

백준 Silver IV | 9012 | Python | 문제 링크

문제 설명

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 '(' 와 ')' 만으로 구성되어 있는 문자열이다. 그 중에서 올바른 괄호 문자열(Valid PS, VPS)은 다음과 같이 정의한다. 한 쌍의 괄호로만 이루어진 "()"가 VPS이고, 만일 x가 VPS라면 "(x)"도 VPS가 된다. 그리고 x와 y가 VPS라면 xy도 VPS가 된다. 입력으로 주어진 괄호 문자열이 VPS인지 판별하시오.

입력

입력 데이터의 수를 나타내는 정수 T가 첫 줄에 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

각 줄마다 해당 입력 괄호 문자열이 VPS 이면 "YES", 아니면 "NO"를 한 줄에 하나씩 출력한다.

입출력 예

입력	출력
6 (()()) (()())((())) (()(()))(()) (()((()) ((()( )	YES YES YES NO NO NO

 

나의 풀이

풀이 1 - 첫 번째 시도와 버그 5개

import sys
input = sys.stdin.readline
stack = []
num = int(input())
for _ in range(num):
    string = sys.stdin
    for c in string:
        if c == "(":
            stack.append("(")
        elif c == ")":
            stack.pop()
    print("NO" if stack else "YES")

제출했더니 런타임 에러가 났다. 뭔가 잘못됐다는 건 알겠는데, 어디가 잘못됐는지는 바로 보이지 않았다.

버그 1 — sys.stdin은 한 줄이 아니다

string = sys.stdin이 눈에 걸렸다. 한 줄을 읽으려고 했는데, sys.stdin은 전체 입력 스트림 객체이다. for c in string으로 순회하면 전체 입력을 다 읽어버린다.

input = sys.stdin.readline으로 바꿔치기를 해뒀으면서, 정작 한 줄을 읽을 때는 sys.stdin을 그냥 쓰고 있었다. input()이라고 쓰면 됐다.

버그 2 — 스택이 비어있는데 pop()을 호출

"())" 같은 입력을 생각해봤다. ( 하나를 push하고, )를 만나 pop한다. 스택이 빈다. 두 번째 )를 만나 또 pop을 시도한다. IndexError가 난다.

스택이 비어있는 상태에서 )를 만났다는 건 이미 틀렸다는 뜻이다. 즉시 False로 확정하고 break해야 했다.

버그 3 — 스택 초기화 위치

stack = []이 루프 바깥에 있었다. 테스트케이스가 여러 개면, 이전 케이스에서 남은 스택이 다음 케이스로 그대로 이어진다. 당연한 실수인데, 코드를 짜는 동안 전혀 의식하지 못했다.

매 테스트케이스마다 스택을 새로 만들어야 한다.

버그 4 — 감지한 걸 덮어씌워버리는 구조

버그 2를 고치면서 이상한 점이 생겼다. ) 초과를 감지하고 continue나 pass로 건너뛰면, 나중에 not stack만 확인하는 상황이 된다.

"())" 케이스에서 어떻게 되는지 따라가봤다. ( push → ) pop → 스택 빔. 두 번째 )는 건너뜀. 루프 종료. 스택이 비어있으니 "YES" 출력. 오답이다.

) 초과를 감지한 순간을 기록해두지 않으면, 나중에 조건을 확인할 방법이 없다. is_valid 플래그로 초과 여부를 기록하고, 마지막에 is_valid and not stack 두 조건을 동시에 확인해야 했다.

유효한 괄호의 조건은 두 가지이다.
1. 중간에 ) 초과가 없어야 한다 — is_valid
2. 마지막에 닫히지 않은 ( 가 없어야 한다 — not stack

하나라도 빠지면 오답이 나온다.

버그 5 — stack[-1] 접근

수정하는 과정에서 stack[-1] == "(" 를 체크하는 코드를 썼다. 이 문제는 (만 push하기 때문에 원소를 확인할 필요가 없다. 개수만 알면 된다. 게다가 빈 스택에서 stack[-1]을 호출하면 역시 IndexError가 난다.

불필요한 코드를 쓰다가 새 버그를 만든 셈이었다.

아찔했던 부분 — \n이 우연히 통과

input = sys.stdin.readline으로 바꿔치기하면 줄 끝의 \n이 제거되지 않는다. for s in string으로 순회하면 마지막에 \n도 s로 들어온다. 그런데 이 문제에서는 \n이 (도 )도 아니라 if/elif 어디에도 걸리지 않는다. 우연히 정답이 나왔다. 엄밀하게는 input().strip()을 써야 맞다.

풀이 2 - 최종 제출 코드

import sys
input = sys.stdin.readline

num = int(input())
result = []

for _ in range(num):
    stack = []
    string = input()
    is_valid = True
    for s in string:
        if s == "(":
            stack.append(s)
        elif s == ")":
            if stack:
                stack.pop()
            else:
                is_valid = False
                break
    if is_valid and not stack:
        result.append("YES")
    else:
        result.append("NO")

print("\n".join(result))

풀이 3 - 리스트 대신 카운터

import sys
input = sys.stdin.readline

num = int(input())
result = []

for _ in range(num):
    string = input().strip()
    stack = 0
    is_valid = True
    for s in string:
        if s == "(":
            stack += 1
        elif s == ")":
            if stack > 0:
                stack -= 1
            else:
                is_valid = False
                break
    result.append("YES" if is_valid and stack == 0 else "NO")

print("\n".join(result))

(만 push하는 경우엔 스택에 실제로 어떤 원소가 들어있는지가 중요하지 않다. 개수만 알면 된다. list 대신 int를 쓰면 메모리를 O(1)로 줄일 수 있다.

스택이라고 하면 리스트를 먼저 떠올리다 보니 이 발상까지 닿지 못했다. 문제를 조금 더 추상적으로 보는 연습이 필요하다는 생각이 들었다.