[바킹독]8. 스택의 활용(수식의 괄호 쌍)

https://youtu.be/cdjjk-ryPKc?si=IXGQTPj6RrDga6Hv

https://blog.encrypted.gg/936

[실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍)

 

1. 수식의 괄호 쌍이란?
2. 문제 해결을 위한 관찰
3. 문제 해결 방법
4. 연습문제 

 

1. 수식의 괄호 쌍이란?

스택의 대표적인 활용 사례 : 수식의 괄호쌍, DFS, Flood Fill... 

위 수식 : 올바른 괄호 쌍

아래 수식 : 올바르지 않은 괄호 쌍

-> 수식의 괄호 쌍 : 주어진 괄호 문자열이 올바른지 판단하는 문제 

2. 문제 해결을 위한 관찰

3. 문제 해결 방법

1) 여는 괄호가 나오면 스택에 추가

2) 닫는 괄호가 나왔을 경우,

2-1) 스택이 비어있으면 올바르지 않은 괄호 쌍

2-2) 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍

2-3) 스택의 top이 짝이 맞는 괄호일 경우 pop 

3) 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호쌍, 남아있지 않으면 올바른 괄호 쌍