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

시간 복잡도

• 배열로 구현 -> 최대 N번 중간에 있는 원소의 삭제 발생 => O(N^2)
• 연결리스트 -> O(N)

=> 스택으로 훨씬 간단하게 구현 

 

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

 

문제 해결 방법

1. 여는 괄호 나옴 -> 스택에 추가
2. 닫는 괄호 나옴
   1. 스택이 비어 있음 -> 올바르지 X 괄호 쌍
   2. 스택의 top이 짝과 맞지 X 괄호 -> 올바르지 X 괄호 쌍
   3. 스택의 top이 짝이 맞는 괄호 -> pop
3. 모든 과정을 끝낸 후 스택에 괄호 남아있음 -> 올바르지 X 괄호 쌍 / 남아있지 X -> 올바른 괄호 쌍

 

---