스택의 활용

스택의 대표적인 활용 사례로 수식의 괄호 쌍이랑 전위/중위/후위 표기법, DFS, Flood Fill 등이 있다. 이 중에서 전위/중위/후위 표기법은 코딩테스트 대비용으로는 너무 지엽적이라 제외한다. 나머지는 다 강의에 포함되어 있고 이번 시간에는 수식의 괄호쌍을 공부해보겠다. 

수식의 괄호쌍이란 주어진 괄호 문자열이 올바른지 판단하는 문제이다. 

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

 

문제 해결 방법

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

이 과정을 보면 가장 최근의 것이 가장 먼저 나오게 된다. 즉 FILO인 것이고 스택 자료구조를 이용해서 구현을 할 수가 있다.