[바킹독의 실전 알고리즘 강의] 스택의 활용 (수식의 괄호 쌍)

수식의 괄호 쌍은 스택을 활용하는 대표적인 문제 유형이다.

수식의 괄호쌍이란 어떤 유형의 문제일까?

 

주어진 괄호쌍이 올바르게 열리고 닫혔는지를 판단하는 문제이다.

 

올바른 괄호 쌍 예시

• (){}
• (({}))
• (){(({}))}

올바르지 않은 괄호 쌍 예시

• ({)}
• ({} 
• ()}

해당 문제를 풀때 다음과 같은 내용을 적용하면 쉽다.

"문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다.

 

문제 해결 방법

1. 여는 괄호가 나오면 스택에 추가
2. 닫는 괄호가 나왔을 경우,
   1. 스택이 비어있으면 올바르지 않은 괄호 쌍
   2. 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍
   3. 스택의 top이 짝이 맞는 괄호일 경우 pop
3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍

 

연습문제

BOJ 4949번 : 균형잡힌 세상

 

BOJ 10799번 : 쇠막대기

 

BOJ 2504번 : 괄호의 값