# 4949. 균형잡힌 세상

📖Problems

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

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

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

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

yes
yes
no
no
no
yes
yes

힌트

7번째의 “ .”와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

🔍Institution

조건

(와 ), [와 ]는 짝이 맞아야 함
모든 닫는 괄호들은 여는 괄호가 존재함
1:1매칭만 가능함. 둘 이상의 괄호와 짝짓지 않음
괄호 안에 있는 문자열도 균형이 잡혀야 한다.
입력의 종료조건 : 맨 마지막에 점 하나(.)

괄호 문제 하면 가장 먼저 떠오르는 것이 어떤 것인가?

바로 스택이다. 특히나, 짝을 맞춰야 하기 때문에 stack을 이용해 짝이 맞는지 비교하면 된다.

flow_ver.1

world라는 이름으로 문자열을 입력받는다.
for문으로 반복하면서 괄호가 있는지 확인한다.
1. 만약에 여는 괄호가 나온다면 → 여는 괄호를 stack에 append한다.
2. 만약 닫는 괄호가 나온다면
  1. 짝이 맞는지 확인한다.
  2. 짝이 맞다면 → stack.pop()한다.
  3. 아니라면 → 짝이 맞지 않은 것이기 때문에 ‘no’를 출력하고 break한다.
종료조건으로 마지막에 점 하나가 들어올 때까지 반복한다.

🔍Approach

제출한 최종 코드

  
while True:
    world = input()
    if world == '.':
        break
    temp = True
    stack = []

    for i in world:
        if i == '(' or i == '[':
            stack.append(i)
        elif i == ')':
            if not stack or stack[-1] == '[':
                temp = False
                break
            elif stack[-1] == '(':
                stack.pop()
        elif i == ']':
            if not stack or stack[-1] == '(':
                temp = False
                break
            elif stack[-1] == '[':
                stack.pop()
        else:
            continue

    if temp == True and not stack:
        print('yes')
    else:
        print('no')

world라는 이름으로 문자열을 입력받는다.
for문으로 반복하면서 괄호가 있는지 확인한다.
1. 만약에 여는 괄호가 나온다면 → 여는 괄호를 stack에 append한다.
2. 만약 닫는 괄호가 나온다면
  1. 짝이 맞는지 확인한다.
  2. 짝이 맞다면 → stack.pop()한다.
  3. 짝이 맞지 않다면 (짝이 맞지 않은 경우는 1. 괄호의 짝이 다르거나 2. 여는 괄호보다 닫는 괄호의 수가 더 많은 경우이다.)
    1. stack이 비어있다면 (= 닫는 괄호의 수가 더 많다면) → temp에 False저장하고 break
    2. 괄호의 짝이 맞지 않다면 → temp에 False저장하고 break
    3. 이는 수행하는 구문이 같기 때문에 같은 조건문으로 연결시켜준다.(if not stack and stack[-1] = ‘(’)
temp에 있는 값이 True라면 yes를 출력하고, False라면 no를 출력한다.
1~3까지 무한 반복한다. 얼마나 들어올지 언제까지 들어올지 모르기 때문이다.
만약 input()으로 점 하나(’ . ’)가 들어온다면 반복문을 종료한다.

아래는 과정을 기록하였다.

🚩 draft code

  
i = ' '
stack = []
while i != '.':
    world = str(input())
    for i in world:
        if i == '(' or i == '[':
            stack.append(i)
        elif i == ')':
            if stack[-1] == '(':
                stack.pop()
            else:
                print('no')
                break
        elif i == ']':
            if stack[-1] == '[':
                stack.pop()
            else:
                print('no')
                break
        else:
            continue

    if stack:
        print('yes')
    else:
        print('no')

수정사항 : 조건문이 올바르지 않음

항상 반복하지만 자꾸 까먹는다.

stack[-1] ==’(’을 비교하는 구문에서 stack에 존재하는지 아닌지 직전 문자열이랑 같은지 아닌지를 파악해야 한다.

flow_ver2.

world라는 이름으로 문자열을 입력받는다.
for문으로 반복하면서 괄호가 있는지 확인한다.
1. 만약에 여는 괄호가 나온다면 → 여는 괄호를 stack에 append한다.
2. 만약 닫는 괄호가 나온다면
  1. 짝이 맞는지 확인한다.
  2. 짝이 맞다면 → stack.pop()한다.
  3. 짝이 맞지 않다면 (짝이 맞지 않은 경우는 1. 괄호의 짝이 다르거나 2. 여는 괄호보다 닫는 괄호의 수가 더 많은 경우이다.)
    1. stack이 비어있다면 (= 닫는 괄호의 수가 더 많다면) → temp에 False저장하고 break
    2. 괄호의 짝이 맞지 않다면 → temp에 False저장하고 break
    3. 이는 수행하는 구문이 같기 때문에 같은 조건문으로 연결시켜준다.(if not stack and stack[-1] = ‘(’)
temp에 있는 값이 True라면 yes를 출력하고, False라면 no를 출력한다.
1~3까지 종료 조건으로 마지막에 점 하나(’.’)가 들어올 때까지 반복한다.

  
i = ' '
while i != '.':
    world = input()
    temp = True
    stack = []

    for i in world:
        if i == '(' or i == '[':
            stack.append(i)
        elif i == ')':
            if not stack or stack[-1] == '[':
                temp = False
                break
            elif stack[-1] == '(':
                stack.pop()
        elif i == ']':
            if not stack or stack[-1] == '(':
                temp = False
                break
            elif stack[-1] == '[':
                stack.pop()
        else:
            continue

    if temp == True and not stack:
        print('yes')
    else:
        print('no')

→ 코드는 정상적으로 실행

문제점 : no일때만 반복해서 받고, yes일 때는 반복이 멈춤, 그게 아니라 .을 입력받아야 종료되어야 한다.

어떻게 바꿔야 할까?

⇒ 가장 마음에 걸렸던 while문의 조건을 수정하였다. 이를 무한반복 실행시키고 종료조건은 if문으로 설정하였다.

🚩Final submission

flow_ver3.

world라는 이름으로 문자열을 입력받는다.
for문으로 반복하면서 괄호가 있는지 확인한다.
1. 만약에 여는 괄호가 나온다면 → 여는 괄호를 stack에 append한다.
2. 만약 닫는 괄호가 나온다면
  1. 짝이 맞는지 확인한다.
  2. 짝이 맞다면 → stack.pop()한다.
  3. 짝이 맞지 않다면 (짝이 맞지 않은 경우는 1. 괄호의 짝이 다르거나 2. 여는 괄호보다 닫는 괄호의 수가 더 많은 경우이다.)
    1. stack이 비어있다면 (= 닫는 괄호의 수가 더 많다면) → temp에 False저장하고 break
    2. 괄호의 짝이 맞지 않다면 → temp에 False저장하고 break
    3. 이는 수행하는 구문이 같기 때문에 같은 조건문으로 연결시켜준다.(if not stack and stack[-1] = ‘(’)
temp에 있는 값이 True라면 yes를 출력하고, False라면 no를 출력한다.
1~3까지 무한 반복한다. 얼마나 들어올지 언제까지 들어올지 모르기 때문이다.
만약 input()으로 점 하나(’ . ’)가 들어온다면 반복문을 종료한다.

  
while True:
    world = input()
    if world == '.':
        break
    temp = True
    stack = []

    for i in world:
        if i == '(' or i == '[':
            stack.append(i)
        elif i == ')':
            if not stack or stack[-1] == '[':
                temp = False
                break
            elif stack[-1] == '(':
                stack.pop()
        elif i == ']':
            if not stack or stack[-1] == '(':
                temp = False
                break
            elif stack[-1] == '[':
                stack.pop()
        else:
            continue

    if temp == True and not stack:
        print('yes')
    else:
        print('no')

🚩Others submission

다른 코드 1

  
 import sys
 while True:
     sen = sys.stdin.readline().rstrip()
     flag = 0
     stack = []
     if sen == '.':
         break
     for i in sen:
         if i == "(" or i == "[": #열린 괄호면 스택에 넣어준다.
             stack.append(i)
         elif i == ")": #닫는 소괄호가 등장했을 때
             if not stack or stack[-1] == "[": #열린 괄호가 없거나 열린 대괄호가 나오면
                 print("no")
                 flag = 1
                 break
             else:
                 stack.pop()
         elif i == "]": # 닫는 대괄호가 등장했을 때
             if not stack or stack[-1] == "(": #열린 괄호가 없거나 열린 소괄호가 나오면
                 print("no")
                 flag = 1
                 break
             else:
                 stack.pop()
     if flag == 0:   #앞서 no가 등장하지 않았을 때
         if not stack :  #스택이 비어있다 = 모든 괄호가 짝을 맞췄다
             print("yes")
         else:
             print("no")

문자열을 처음부터 차례대로 검사하는데, 괄호가 등장하면 stack에 넣어준다.

1. 소괄호를 닫을 때 스택이 비어있거나, 스택의 top이 대괄호이면 잘못된 문장이다.

2. 대괄호를 닫을 때 스택이 비어있거나, 스택의 top이 소괄호이면 잘못된 문장이다.

3. 열린 괄호가 닫힌 괄호보다 많이 등장한다. ( 마지막에 stack이 비어있지 않을 때 )

이 세가지 경우를 제외하고는 짝을 맞춰 괄호가 등장한다.

인터넷에서 찾은 코드들 대부분 다 무한반복을 실행해서 코드를 작성하였다.

💡Retrospect

스택 부분에 있어서는 반복학습을 많이 했음에도 !!! 자꾸 놓치는 부분이 있다. 자꾸 같은 부분을 놓친다. 오늘은 확실하게 체크해두어야겠다.
그래도 이런 비슷한 문제를 많이 풀었기에 체감난이도는 낮았다.

백준 - 4949. 균형잡힌 세상 (MJ)

# 4949. 균형잡힌 세상

📖Problems

힌트

🔍Institution

🔍Approach

🚩 draft code

🚩Final submission

🚩Others submission

💡Retrospect

Further Reading

백준 - 10733. 제로 (MJ)

백준 - 2493. 탑 (MJ)

백준 - 1920. 수 찾기(MJ)