짝 찾기 문제와 스택의 본질

1. 짝 찾기 문제

문제는 아래와 같다.

( 또는 ) 로만 구성된 문자열 s가 주어진다. 문자열 s가 올바른 괄호이면 true를 return하고, 올바르지 않다면 false를 return 하는 solution 함수를 작성하라.

괄호가 바르게 짝 지어졌다는 것은 ( 문자로 열렸다면 반드시 ) 문자로 닫혀야 한다는 뜻이다. 예를 들어, "()()" 는 올바른 문자열이다. "(())()" 도 올바른 문자열이다.

문제의 해답은 스택을 사용하면 아주 쉽게 풀린다. 아이디어도 매우 간단하다.

문자열을 순서대로 접근해 스택에 넣는다. 이때 닫는 괄호 )가 나오면 스택에서 데이터를 하나 pop 하자. 해당 문자 ( 는 이제 처리되어 소거된다. 이런 논리를 계속 반복하다보면 문자열 접근이 완료되면 스택도 전부 비어있게 된다. 만약 문자열을 전부 순회했는데도 스택에 데이터가 남아있다면, 해당 괄호 (은 닫는 괄호를 만나지 못한 것이므로 잘못된 문자열이다.

 

2. 왜 스택이 사용되는 것일까?

그런데 왜 스택 자료구조가 위와 같은 짝 찾기 문제에 활용될 수 있는 것일까? 표면적으로 생각하지 말고 본질에 접근하자.

이전에 작성했던 포스트에서 스택의 본질에 대해 공부한 것을 정리한 바 있다.

스택 자료구조의 본질과 진정한 의미

 

스택 자료구조는 단순히 데이터를 적재하는 구조가 아니다. 스택은 컴퓨터의 전형적인 문제 해결 방법인, "큰 문제를 분할해 작은 문제로 만들어 작은 문제들을 먼저 해결해나가며 최종 문제로 되돌아가 해결하는 방식"을 지원해주는 자료구조다.

짝 찾기 문제는 단순히 짝을 찾는 문제라고 생각하지 말고 괄호의 우선순위를 생각해보면 왜 그것이 스택을 요구하는지 쉽게 알 수 있다.

괄호 문자 ()은 일종의 처리를 나타내는 상징으로 볼 수 있다. ( 기호는 어떤 처리(함수)를 상징하며, 따라서 어떤 처리가 시작되었다는 신호다. 이때 괄호는 중첩될 수 있다. 이것은 먼저 시작된 처리를 큰 문제라고 보면 새로운 ( 기호는 큰 문제 밑에 있는 분할된 작은 문제의 시작점으로 볼 수 있는 것이다. (()) 기호는 겉에 있는 큰 문제가 자신의 문제를 시작하며 작은 문제를 호출한 구조와 동일한 것이다. 

만약 큰 문제가 작은 문제 2개로 분할했다면, 기호는 (()()) 가 될 수 있는 것이다! 

결국 괄호는 컴퓨터의 문제 해결 방식을 상징적으로 기호로 나타낸 것이라 할 수 있다. '('은 처리의 시작을 의미하고, ')'은 해당 처리의 종료를 의미한다. 따라서 ')'을 만났을 때, 가장 하위의 문제를 해결한다. 그리고 ')' 기호들을 연속해서 만난다면 그것은 기존의 문제들을 해결하면서 최종적인 큰 문제로 복귀한다는 것이다. 

스택 그 자체다. 스택의 본질이 큰 문제를 작은 문제로 분할하고, 작은 문제를 먼저 해결해나가며, 나중에 최종적으로 큰 문제를 시작한 곳으로 되돌아가는 프로세스 플로우를 지원해주는 구조라는 것을 알고 있다면 짝 찾기 문제가 스택을 요구하는 것은 전혀 의문스럽지 않다.