[BOJ] 4949번: 균형잡힌 세상 | Python

About Algorithm

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호(“()”) 와 대괄호(“[]”)로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

  • 모든 왼쪽 소괄호(“(“)는 오른쪽 소괄호(“)”)와만 짝을 이뤄야 한다.
  • 모든 왼쪽 대괄호(“[“)는 오른쪽 대괄호(“]”)와만 짝을 이뤄야 한다.
  • 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
  • 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
  • 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
  • 정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호(“( )”) 대괄호(“[ ]”)등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(“.”)가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 “yes”를, 아니면 “no”를 출력한다.

풀이

안에 있는 괄호 짝이 먼저 맞아야 하므로, 스택을 이용하여 풀면 되는 문제.

처음 답

  • 28776KB / 412ms

처음 했던 코드는 아래 코드인데, 결과는 맞게 나오지만 시간이 짧은 편이 아니고 가독성이 그리 좋지 않았다. 이것보다는 훨씬 시간을 단축하고 간결하게 할 수 있을 것 같아서, 다른 답안들도 참고하였더니 역시나 훨씬 간결하게 줄일 수 있는 요소들이 많았다.

while True:
  stk = []
  words = list(input())
  if len(words)==1 and words[0]=='.' : break

  for i in words:
    if i=='(' or i==')' : stk.append(i)

    elif i == ')':
      if len(stk)>0 and stk[-1] =='(' : stk.pop()
      else: stk.append(i); break

    elif i == ']':
      if len(stk)>0 and stk[-1] =='[' : stk.pop()
      else: stk.append(i); break

  if len(stk) == 0 : print('yes')
  else: print('no')

발전된 답

  • 28776KB / 92ms

i가 ‘(‘ 또는 ‘[’ 인지 확인할 때는 i in '(['로 줄일 수 있는 점, 리스트가 비어있는지 확인할 때는 그냥 not stk 하면 되는 점 등등 간단하지만 몰랐던 것들을 알게되었다,,, 또, 앞으로 그냥 짜는 것보다는 함수를 정의하고 입력을 받아 그 함수를 호출하는 식으로 짜려고 노력해야겠다.

from sys import stdin, stdout

def left(right):
  return '(' if right==')' else '['

def isBalanced(s):
  stk = []
  for i in s:
    if i in '([': stk.append(i)
    elif i in ')]':
      if not stk or stk[-1] != left(i): return False
      else: stk.pop()

  return not stk

while True:
  s = stdin.readline().rstrip()
  if s == '.': break
  stdout.write('yes\n' if isBalanced(s) else 'no\n')