4949: 균형잡힌 세상 - Python

문제

https://www.acmicpc.net/problem/4949

풀이 1 (오답)

from collections import deque

while True:
    s = input()
    if s == ".":
        break

    stack = deque()
    for c in s:
        if c == "[" or c == "(":
            stack.append(c)
        elif c == "]":
            if stack and stack[-1] == "[":
                stack.pop()
        elif c == ")":
            if stack and stack[-1] == "(":
                stack.pop()
    
    if not stack:
        print("yes")
    else:
        print("no")

• 오답이다. ()), ([)과 같은 case에 대해 오동작한다.

풀이 2 (정답)

from collections import deque

while True:
    s = input()
    if s == ".":
        break
        
    stack = deque()
    for c in s:
        if c == "(" or c == "[":
            stack.append(c)
        elif c == ")":
            if not stack or stack[-1] == "[":
                stack.append(c)
                break
            else:
                stack.pop()
        elif c == "]":
            if not stack or stack[-1] == "(":
                stack.append(c)
                break
            else:
                stack.pop()
    
    if not stack:
        print("yes")
    else:
        print("no")	

• 분명 더 간단한 코드가 있을 것 같은데.. 어찌 구현해야 할지 모르겠다.
• 특히 ), ]가 잘못 들어왔을 때 append하는 게 아니라 바로 "no"를 출력하고 반복문을 탈출하고 싶은데 그게 안된다.

풀이 3

from collections import deque

while True:
    s = input()
    if s == ".":
        break

    stack = deque()
    flag = 0
    for c in s:
        if c == "(" or c == "[":
            stack.append(c)
        elif c == ")":
            if not stack or stack.pop() != "(":
                flag = -1
                break
        elif c == "]":
            if not stack or stack.pop () != "[":
                flag = -1
                break
    
    if flag == -1 or stack:
        print("no")
    else:
        print("yes")

• append하는 대신 flag 변수를 사용했다.
  규칙에 맞지 않는 문자열일 경우 flag = -1로 설정하고 for문을 나온다.
  만약 flag = -1이거나 스택이 비어있지 않으면 "no"를 출력한다.

-> 다른 풀이들 찾아보니 풀이 2 또는 풀이 3과 비슷하게들 푼 것 같다.

풀이 4 (greene님 풀이)

while True:
  str = input()
  check = ''
  answer = 'yes'
  if str == '.':
    break
  for s in str:
    if s not in '()[]':
      continue
    else:
      check += s
  for _ in range(len(check)//2+1):
    check = check.replace('()', '')
    check = check.replace('[]', '')
  if len(check):
    print('no')
  else:
    print('yes')

• 천재적인 아이디어!

1. 전체 문자열에서 "(", ")", "[", "]" 문자들만 가져와 check라는 문자열에 저장한다.
2. 문자열 내 모든 괄호들이 순서대로 저장된 check에서 (), []쌍을 찾아 지운다.
3. 만약 check에 지워지지 않은 괄호가 있다면 "no"를, check가 비어있다면 "yes"를 출력한다.