백준 4949 파이썬 풀이

안녕하세요 호박감자입니다.

이번엔 4949번 풀이를 리뷰하겠습니다.

스택을 사용한 코드로, 간략히 만 설명하겠습니다.

---

import sys
input = sys.stdin.readline

sentence = input()
while sentence != '.\n':
    stack = []
    for s in sentence:
        if s == '(':
            stack.append('(')
        elif s == '[':
            stack.append('[')
        elif s == ')':
            if not stack or stack.pop() != '(':
                print('no')
                break
        elif s == ']':
            if not stack or stack.pop() != '[':
                print('no')
                break
    else:
        print('yes' if not stack else 'no')
    sentence = input()

리스트 자료형을 사용해 스택을 구현해줍니다.

그리고 소괄호나 대괄호의 여는 괄호가 나오면 스택에 넣어줍니다.

닫는 괄호가 나올 때는 스택을 pop 해서 최근 스택에 들어간 문자와 짝이 맞는지를 확인합니다.

스택을 사용하는 이유는 소괄호면 소괄호, 대괄호면 대괄호의 짝을 맞추기 위해서입니다.

가령 문자열이 다음과 같다고 해봅시다.

hi (hello) fruit ( apple [ red ) orange]

그러면 스택에는 가장 처음 ' ( ' 여는 소괄호가 들어오게 될 것입니다. 그리고 닫는 소괄호가 오게 되면 pop()을 합니다.

pop()을 하면 스택에 들어있던 ' ( '가 나오게 됩니다. 소괄호와 소괄호니 짝이 맞습니다.

그다음 스택에는 fruit 다음의 ' ( '가 들어옵니다. 그리고 apple 다음의 ' [ '가 들어옵니다.

그리고서는 닫는 소괄호 ' ) '를 만나게 됩니다. 그러면 pop()을 합니다.

pop()을 하면 가장 나중에 스택에 들어간 ' [ ' 대괄호가 나오게 됩니다. 소괄호와 대괄호니 짝이 안 맞죠? 이렇게 되는 경우는 틀리게 되는 경우이므로 이를 위해 후입 선출인 스택 구조체를 사용해야 합니다.

그리고 주의할 점은 sys.stdin.readline을 사용해서 입력을 받기 때문에 매 문장의 끝에 줄 바꿈 기호( \n )가 있습니다. 이를 유념해서 코드를 짜야합니다.

4949 코드 리뷰는 여기까지 하겠습니다.