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

수식의 괄호 쌍이란?

위 식은 계산이 가능한 올바른 식이지만, 아래 식은 괄호가 이상하게 배치되어 있다.

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

 

문제 해결을 위한 관찰

• 보편적인 방법으로는, 안쪽부터 짝 맞추기를 해서 괄호를 지워나가는 방법이다.
  짝이 모두 맞으면 올바른 괄호 쌍이고, 그렇지 않으면 올바르지 않은 괄호 쌍이다.
• )의 개수가 (의 개수를 넘지 않아야 한다.

 

괄호가 여러 종류일 때에는 여는 괄호와 닫는 괄호의 개수만으로는 판단할 수 없다.

대신 짝이 되는 소괄호() 와 중괄호{} 를 지우는 방법은 여전히 잘 동작한다.

 

이 방법은 배열로 구현할 경우, 최대 N번 중간에 있는 원소의 삭제가 발생하기 때문에 O(N²)이고

연결리스트로 구현할 경우, O(N)이다.

스택을 이용할 경우, 배열이나 연결리스트보다 간단하게 구현할 수 있다.

 

스택을 이용하기 위해 필요한 추가 관찰

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

 

문자열을 다 읽었고, 남아있는 괄호가 없다면 모든 괄호의 짝이 다 맞았다는 것을 알 수 있다.

즉, 여는 괄호를 읽을 때마다 저장하다가 닫는 괄호를 읽을 때 가장 최근에 들어온 여는 괄호를 pop하여 올바른 괄호 쌍인지 확인할 수 있다.

 

문제 해결 방법

여는 괄호가 나오면 저장해 뒀다가 닫는 괄호가 나오면 짝이 맞는지 확인한 후, 가장 최근에 들어온 여는 괄호를 제거하는 방식으로 진행한다.

이 과정은 가장 최근의 것이 먼저 나오게 됨을 알 수 있다.

즉 FIFO인 것이고, 스택 자료구조를 이용해서 구현할 수 있다.

 

정리

1. 여는 괄호가 나오면 스택에 추가한다.

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

• 스택이 비어있으면 올바르지 않은 괄호 쌍
• 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍
• 스택의 top이 짝이 맞는 괄호일 경우 pop

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

    남아있지 않으면 올바른 괄호 쌍

 

 

출처: 바킹독님 블로그