- 균형잡힌 문자열이란?
- 모든 소괄호와 대괄호는 짝을 이루어야 함.
- " ( " 와 " ) ", " [ " 와 " ] " 가 짝을 이룸.
- 모든 괄호들은 1 : 1 매칭만 가능함.
- 어떠한 괄호 사이에 있는 문자열도 균형이 잡혀야 함.
[입력]
- 점 하나 (" . ") 만 들어올때까지 계속해서 문자열을 입력.
[출력]
- 각 입력줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력.
stack을 사용해 쉽게 해결할 수 있는 문제이다.
소괄호( " () " ) 와 대괄호 ( " [] " ) 들이 균형맞게 입력되어있으면 된다.
이 조건을 확인하는 방법은 아래와 같다.
- 어떠한 종류의 괄호라도 여는 괄호 ( "(", "[" ) 라면 stack에 push 한다.
- 닫는 괄호가 입력되었을 때 ( ")", "]" ) stack이 비어있다면 균형이 깨진 문자열이 된다.
- 닫는 소괄호 ( ")" ) 가 입력되었을 때 stack의 top에는 여는 소괄호
( "(" ) 가 존재해야 하고, 대괄호도 닫는 대괄호 ( "]" ) 가 입력되었을 때 stack의 top에는 여는 대괄호 ( "[" ) 가 존재해야 한다.
위의 조건을 코드로 작성하면 다음과 같다.
위와 같은 과정을 거친 후 stack이 비어있다면 균형잡힌 문자열이므로 "yes" 출력, stack이 비어있지 않으면 "no" 출력
( ∵ 짝이 맞는 괄호는 여는 괄호를 pop을 하므로 짝이 맞다면, 즉 균형잡힌 문자열이라면 stack이 비어있어야 함. )