[C++] 백준 4949번 풀이 (균형잡힌 세상)

- 문제 (4949번) : 균형잡힌 세상

• 링크 : https://www.acmicpc.net/problem/4949

• 입력받은 문자열이 균형잡힌 문자열인지 판단하는 문제

  • 균형잡힌 문자열이란?
    • 모든 소괄호와 대괄호는 짝을 이루어야 함.
    • " ( " 와 " ) ", " [ " 와 " ] " 가 짝을 이룸.
    • 모든 괄호들은 1 : 1 매칭만 가능함.
    • 어떠한 괄호 사이에 있는 문자열도 균형이 잡혀야 함.

---

- 입력 및 출력

[입력]

• 점 하나 (" . ") 만 들어올때까지 계속해서 문자열을 입력.

[출력]

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

---

- 문제 풀이

• stack을 사용해 쉽게 해결할 수 있는 문제이다.

  소괄호( " () " ) 와 대괄호 ( " [] " ) 들이 균형맞게 입력되어있으면 된다.
  이 조건을 확인하는 방법은 아래와 같다.

  • 어떠한 종류의 괄호라도 여는 괄호 ( "(", "[" ) 라면 stack에 push 한다.
  • 닫는 괄호가 입력되었을 때 ( ")", "]" ) stack이 비어있다면 균형이 깨진 문자열이 된다.
  • 닫는 소괄호 ( ")" ) 가 입력되었을 때 stack의 top에는 여는 소괄호
    ( "(" ) 가 존재해야 하고, 대괄호도 닫는 대괄호 ( "]" ) 가 입력되었을 때 stack의 top에는 여는 대괄호 ( "[" ) 가 존재해야 한다.

• 위의 조건을 코드로 작성하면 다음과 같다.

  

• 위와 같은 과정을 거친 후 stack이 비어있다면 균형잡힌 문자열이므로 "yes" 출력, stack이 비어있지 않으면 "no" 출력
  ( ∵ 짝이 맞는 괄호는 여는 괄호를 pop을 하므로 짝이 맞다면, 즉 균형잡힌 문자열이라면 stack이 비어있어야 함. )

---

- 최종 코드