[백준 / 4949] 균형잡힌 세상

in Problem Solving on BaekJoon


날짜: 2021년 6월 21일
소요 시간: 1시간 12분 49초
카테고리: 스택, 문자열, 수학문제
태그: silver.4, 4949, 파이썬

백준 4949 - 균형잡힌 세상

입출력 예시

예제 입력예제 출력
So when I die (the [first] I will see in (heaven) is a score list).yes
[ first in ] ( first out ).yes
Half Moon tonight (At least it is better than no Moon at all].no
A rope may form )( a trail in a maze.no
Help( I[m being held prisoner in a fortune cookie factory)].no
([ (([( [ ] ) ( ) (( ))] )) ]).yes
.yes
. 

내가 적은 코드

import sys

class Stack:
    def __init__(self):
        self.items = []
    def push(self, val):
        self.items.append(val)
    def pop(self):
        if self.isEmpty():
            print("stack is empty")
        else:
            return self.items.pop()
    def top(self):
        if not self.isEmpty():
            return self.items[-1]
    def __len__(self):
        return len(self.items)
    def isEmpty(self):
        is_empty = False
        if len(self.items) == 0:
            is_empty = True
        return is_empty

arr = []

while True:
    line = sys.stdin.readline().rstrip()
    if line == '.':
        break
    else:
        arr.append(line)

stack = Stack()

for j in arr:
    stack = Stack()
    for i in str(j):
        if i == "[" or i == "(":
            stack.push(i)
        elif i == "]":
            if stack.top() == "[":
                stack.pop()
            else:
                print("no")
                break
        elif i == ")":
            if stack.top() == "(":
                stack.pop()
            else:
                print("no")
                break
        elif i == ".":
            if stack.isEmpty():
                print("yes")
            else:
                print("no")

풀이 과정

분명 더 짧게 풀 수 있지만 이번 기회에 스택을 실제로 구현해 보는 연습을 하기 위해 클래스로 스택을 구현해놓고 문제를 풀었다.

Stack클래스로 스택을 구현하고 문제를 접근했다.
여러 줄이 입력될 경우도 있다고 하였으니, 문자열을 line에 저장하고 그 line을 arr에 저장한다.
입력의 종료 조건인 .이 나올 때 까지 문자열을 arr에 저장한다.

그리고 문자열을 반복문을 통해 괄호가 열리는 (나 [가 나올 때 까지 문자들을 검사한다.
그리고 괄호가 닫히는 (나 [가 나올 시 stack에 push한다.
만약 stack의 top에 있는 괄호의 종류와 검사한 괄호의 종류가 맞지 않거나 stack이 비어있는데 닫히는 괄호가 나올 시 “no”를 출력하고 반복을 break 한다.

만약 괄호가 닫히는 )나 ]가 나올 시
stack의 top이 (나 [인지 확인하고 같은 종류의 괄호라면 pop하게 끔 만들었다.
그리고 문자열의 마지막을 알리는 .이 나온다면 isEmpty()함수를 통해 stack이 비어있는지 확인 후 비어있다면 “yes”를 아니라면 “no”를 출력한다.

베스트 코드

from sys import stdin, stdout

def isvalid(s):
    stack = []
    for c in s:
        if c in '([':
            stack.append(c)
        elif c == ')':
            if not stack or stack.pop() != '(':
                return False
        elif c == ']':
            if not stack or stack.pop() != '[':
                return False
    return not stack

strings = stdin.readlines()
strings.pop()
for string in strings:
    stdout.write("yes\n" if isvalid(string) else "no\n")

반성

  • 스택에 대해서 이론적으로 이해하고 있다고 생각해서 크게 신경쓰지 않았는데 막상 코드로 구현하려고 했을 때 오류가 많이 나서 버벅였다. 앞으로 다른 자료구조를 공부해도 보다 확실히 체득할 때 까지 코드로 구현해 볼 필요가 있다.


© 2021. by hminkim