스택 practice 01 _ 균형잡힌 세상

백준 4949번 

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

4949번: 균형잡힌 세상

 

 

 

1. 문제

 

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

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

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

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

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

 

2. 내가 작성한 알고리즘

import sys
 
while 1:
      word=sys.stdin.readline().rstrip()
      if word==".":
            break
 
      arr=[]
      temp=1
      
      for i in range(len(word)):
            if word[i] in {'[','('}:
                  arr.append(word[i])
            elif arr and (word[i]==')' or word[i]==']'):
                  if arr[-1]=='[' and word[i]==']':
                        arr.pop()
                  elif arr[-1]=='(' and word[i]==')':
                        arr.pop()
                  else:
                        temp=0
                        
            elif not arr and ( word[i]==']' or word[i]==')'):
                  temp=0
      if temp and not arr:
                  print("yes")
      else:
                  print("no")
                  
      
                        
 

 

 

3. 이번 알고리즘을 통해 배운 점

1. 속도 향상을 위해 input() 대신 import sys 를 통해 sys.stdin.readline() 을 사용

2. sys.stdin.readline()은 줄 바꿈 문자가 포함되기 때문에 strip() 함수를 추가로 사용

3. 입력받은 문자만큼 반복한다. (문자 하나씩 확인한다.)

   3.1 만약 열기 문자가 있다면 arr배열에 저장한다. ex) ' [ ', ' ( '

   3.2 만약 arr배열에 수가 있고 닫기 문자가 나오면 arr맨 끝 문자와 비교한다. 

     3.2.1 arr[-1]에  ' [ ' 가 있고 닫기 문자가 ' ] ' 면 pop()함수를 통해 ' [ ' 열기 문자를 삭제

     3.2.2 arr[-1]에  ' ( ' 가 있고 닫기 문자가 ' ) ' 면 pop()함수를 통해 ' ( ' 열기 문자를 삭제

     3.2.3 둘 다 해당하지 않을 경우 거짓

  3.3  만약 arr배열에 수가 없을 때 닫기 문자가 나오면 그 문자열은 거짓 

 

-> 스택의 개념을 다시 배우게 된 시간이었다. 반복문을 통해 각각의 문자들을 추출하고 저장하여 비교하는 알고리즘과 스택의 개념이 배합된 알고리즘으로 반복되는 응용문제에 주의해야 될 것 같다.