[4949] 균형잡힌 세상

 

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

문제 설명

세계는 균형이 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 모든 다른 것들도 균형이 잡혀있어야 한다. 문자열에 포함되는 괄호는 소괄호("()")와 대괄호("[]")로 이루어져 있으며, 이 문자열이 균형을 이루는지를 판별하시오.

입력

각 문자열은 마지막 줄을 제외하고는 '.' 을 제외한 아스키 문자로 이루어져 있으며, 문자열의 길이는 100 이하이다. 입력의 종료조건으로 "."만으로 이루어진 줄이 주어진다.

출력

각 줄마다 해당 문자열이 균형잡힌 문자열이면 "yes"를, 아니면 "no"를 출력한다.

입출력 예

입력	출력
() [] ([)] .	yes yes no

 

나의 풀이

풀이 1 - 세 가지 버그 수정 과정

import sys
result = []
for line in sys.stdin:
    stack = []
    is_valid = True
    for s in line:
        if s == "(" or s == "[":
            stack.append(s)
        elif s == ")":
            if stack and stack[-1] == "(":
                stack.pop()
            else:
                is_valid = False
                break
        elif s == "]":
            if stack and stack[-1] == "[":
                stack.pop()
            else:
                is_valid = False
                break
    if is_valid and not stack:
        result.append("YES")
    else:
        result.append("NO")
print("\n".join(result))

9012번 괄호 문제를 푼 직후였다. 문제 목록에서 4949번을 보는 순간, 비슷한 유형이라는 걸 바로 알 수 있었다. 스택으로 괄호 짝을 맞추는 구조. 이미 한 번 해본 패턴이었다. 거의 확신에 가까운 상태로 코드를 작성했고, 제출했다.

틀렸습니다.

고치고 또 제출해도 틀렸고, 다시 고치고 제출해도 틀렸다. 나중에야 알고 보니 독립된 버그가 세 개가 동시에 들어가 있었다.

버그 1 — 문제를 끝까지 안 읽었다

9012번은 첫 줄에 테스트케이스 수 n이 주어진다. n번 반복하면 된다. 4949번은 달랐다. 마지막 줄이 . 하나일 때 입력이 끝난다. 그냥 .이 나올 때까지 계속 읽으면 된다.

종료 조건이 아예 없었다. 그러니 . 한 줄도 테스트케이스로 처리됐다. .은 괄호가 없고 스택도 비어있으니 is_valid가 True, 결과 리스트에 "YES"가 하나 더 붙었다.

문제 조건을 꼼꼼하게 확인하지 않은 것이다. 비슷한 문제라고 판단한 순간부터 이미 주의를 덜 기울이게 됐다.

for line in sys.stdin:
    if line.rstrip() == ".":
        break

버그 2 — strip()과 rstrip()을 구분하지 않았다

종료 조건을 넣고 나서, 처음에는 strip()을 썼다.

if line.strip() == ".":
    break

strip()은 문자열 앞뒤의 공백을 모두 제거한다. 그러면 " ." 같은 줄, 즉 앞에 공백이 있고 뒤에 온점이 있는 문자열이 "."과 같아져버린다. 그런데 " ." 은 정상적인 테스트케이스이다. 공백은 괄호가 아니니까 무시되고, 전체적으로 균형잡힌 문자열이다. 이 줄을 종료 신호로 잘못 해석하면 테스트케이스 하나를 통째로 건너뛰게 된다.

rstrip()은 오른쪽 끝의 공백과 줄바꿈 문자만 제거한다. 앞에 있는 공백은 건드리지 않는다. 종료 조건은 "온점 하나짜리 줄"이지, "공백 제거 후 온점"이 아니다. 미묘한 차이였지만 결과는 달랐다.

버그 3 — 출력 형식을 확인하지 않았다

이것이 가장 허탈했다.

9012번의 출력은 YES와 NO이다. 대문자이다. 그래서 그냥 쓴 것이다. 출력 조건을 다시 확인할 생각을 못 했다.

4949번의 출력은 yes와 no이다. 소문자이다.

백준은 대소문자를 구분해서 채점한다. YES는 오답이다. 코드 로직이 완벽히 맞아도 출력 형식이 틀리면 전부 틀린 것이다. 나중에 이걸 발견했을 때 할 말이 없었다.

풀이 2 - 최종 제출 코드

import sys

result = []
for line in sys.stdin:
    if line.rstrip() == ".":
        break

    stack = []
    is_valid = True
    for s in line:
        if s == "(" or s == "[":
            stack.append(s)
        elif s == ")":
            if stack and stack[-1] == "(":
                stack.pop()
            else:
                is_valid = False
                break
        elif s == "]":
            if stack and stack[-1] == "[":
                stack.pop()
            else:
                is_valid = False
                break

    if is_valid and not stack:
        result.append("yes")
    else:
        result.append("no")

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

2종류 괄호를 처리하는 핵심은 stack and stack[-1] == "(" 에서 and의 단락 평가이다. 스택이 비어있으면 stack이 False이므로 stack[-1]을 실행하지 않는다. 비어있는 리스트에 [-1]을 쓰면 IndexError가 나는데, and가 앞에서 막아준다.

9012번과 미묘하게 다른 포인트들을 정리하면:

항목	9012번	4949번
괄호 종류	( ) 1종류	( ) [ ] 2종류
입력 방식	테스트케이스 수 n이 주어짐	. 하나로 종료
출력 형식	YES / NO (대문자)	yes / no (소문자)

비슷한 문제일수록 차이를 더 의심해야 한다는 걸, 세 번 틀리고 나서야 체감했다.