[python] 4949. 균형잡힌 세상

• 문제

 

 

• 잘못된 풀이 (런타임 에러)

런타임 에러
command = ['(', ')', '[', ']']

while True:
    string = input()
    if string == '.':
        quit()

    for i in string:
        if i in command:
            if i == '(':
                check1 = 1
            elif i == ')':
                if check2 == 1:
                    check1 = 1
                else: check1 = 0
            elif i == '[':
               check2 = 1
            elif i == ']':
                check2 = 0

    if check1 == 0 and check2 == 0:
        print("yes")
    else:
        print("no")

 

해당 문제는 문자열을 다루는 문제이다.

처음에는 해당 문제를 check1, check2 변수를 통해 '()'와 '[]'의 짝을 체크하는 방법으로 해결하였다.

결과적으로 계속된 출력 초과와 런타임 에러로 문제를 해결하지 못했다. (출력은 올바르게 되는데 왜 오류가 뜨는지는 모르겠다 ..)

 

따라서 새로운 방법을 생각했고, stack 자료구조를 통해 문제를 풀 수 있었다. 

 

 

• 올바른 풀이

while True:
    string = input()
    stack = []

    if string == ".":
        break

    for i in string:
        if i == '[' or i == '(':
            stack.append(i)
        elif i == ']':
            if len(stack) != 0 and stack[-1] == '[':
                stack.pop()
            else :
                stack.append(']')
                break
        elif i == ')':
            if len(stack) != 0 and stack[-1] == '(':
                stack.pop()
            else:
                stack.append(')')
                break
    if len(stack) == 0:
        print('yes')
    else:
        print('no')

 

while문을 통해 입력을 계속 받고, 입력의 종료조건인 '.'이 들어오면 입력을 멈춘다.

그리고 해당 문자열을 하나씩 보면서 '[' 혹은 '('가 입력으로 들어왔을 때, stack에 쌓는다. 

stack의 마지막 원소(가장 최근의 입력)을 보고, 짝이 맞는 괄호가 입력으로 들어오면 pop하여 stack을 비워준다.

짝이 맞지 않은 괄호가 입력으로 들어오면 stack에 쌓는다.

이렇게 반복하고 최종적으로 stack이 비어있으면 yes를 출력하고, 아니면 no를 출력한다.

 

해당 문제를 stack 자료구조를 통해 해결하면 비교적 쉽게 해결할 수 있다.

 

한가지 더 언급할 사항이 있다면, 처음에는 원래 while문에서 입력을 input()이 아니라 sys.stdin.readline()을 통해서 받으려고 하였다.

시간복잡도가 input()보다 sys.stdin.readline()이 더 작기/빠르기 때문이다.

하지만 입력을 readline()을 통해서 받으면 출력오류가 난다. 때문에 입력은 input()으로 받아주었다.