c++ 알고리즘 공부 8 - 스택활용

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

 

저희가 눈으로 보면 괄호 문자열이 올바른지 아닌지 판단할 수 있습니다. 그런데 혹시 머릿속에서 어떤 로직을 거쳐서 판단을 하시나요? 우리는 이걸 코드로 구현해내는게 목표이니 로직을 잘 생각해볼 필요가 있습니다. 쉬운 것 부터 하나씩 해보는게 좋을 것 같아서 일단 괄호의 종류가 1개인 경우만 다뤄보겠습니다.

 

그런데 괄호가 여러 종류일 때에는 여는 괄호의 갯수와 닫는 괄호의 갯수 만으로는 해결이 되지 않습니다. 예를 들어서 지금 슬라이드의 저 두 괄호 문자열을 생각해보면 위는 올바르고 아래는 올바르지 않습니다. 그런데 둘 다 ) 의 갯수가 ( 을 넘은 적도 없고, } 의 갯수가 { 을 넘은 적도 없었습니다.

 

대신 붙어있는 ( ) 혹은 { } 를 지우는 방법은 여전히 잘 동작합니다. 이 방법은 배열로 구현할 경우 최대 N번 중간에 있는 원소의 삭제가 발생하기 때문에 O(N2)이고, 연결 리스트로 구현할 경우 O(N)입니다. 배열은 시간 복잡도가 안좋으니 거르고, 연결 리스트로 구현은 해볼만하니까 한 번 짜보셔도 좋습니다. 그런데 스택을 이용하면 훨씬 더 간단하게 할 수 있습니다. 이 방법을 고안하려면 하나의 관찰이 추가로 더 필요합니다.

 

그 관찰은 바로 "문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다" 입니다. 이걸 듣고 흠칫했다면 좀 많이 대단한거지만 그러기가 쉽지 않을테니 예시를 보겠습니다. 이해를 돕기 위해 짝이 맞는 애들은 색깔로 표시를 해놨습니다. 이제 진행을 해보겠습니다.

 

그 다음으로 있는 3개는 닫는 괄호이니 차례로 지우면 되겠죠. 문자열을 다 읽었고 남아있는 괄호가 없는 것으로 보아 모든게 다 짝이 잘 맞았다는걸 알 수 있습니다. 이처럼 올바른 괄호 쌍일 경우 여는 괄호를 읽을 때 마다 저장하다가 닫는 괄호를 읽을 때 가장 최근에 들어온, 즉 가장 끝에 있는 여는 괄호와 짝을 이루게 해주고 pop을 하면 올바른 괄호 쌍인지 확인할 수 있습니다.

 

그러면 올바르지 않은 괄호 쌍에서는 이 알고리즘이 어떤 식으로 동작하는지 같이 살펴보겠습니다.

 

 

첫 번째로 짝이 맞지 않는 경우를 살펴보겠습니다. 일단 처음 2개 괄호는 여는 괄호이니 그냥 쓰면 됩니다. 그 다음 괄호는 닫는 괄호이니 가장 최근에 들어온 여는 괄호와 짝을 지어야합니다. 그런데 여기서 문제가 생겼습니다. 여는 괄호는 중괄호인데 닫는 괄호는 소괄호입니다. 이렇게 되면 둘은 짝을 지을 수가 없습니다. 그래서 우리는 지금 이 문자열이 올바르지 않은 괄호 쌍임을 알 수 있게 됩니다. 

 

올바르지 않은 괄호 쌍의 두 번째 예시를 보겠습니다. 일단 처음 2개 괄호는 여는 괄호이니 그냥 쓰면 됩니다. 그 다음 괄호는 닫는 괄호이니 가장 최근에 들어온 여는 괄호와 짝을 지을거고 둘 다 중괄호니 별 문제는 없습니다.

 

이렇게 문자열을 끝까지 읽었는데 아직 처리를 하지 못하고 남아있는 여는 괄호가 있습니다. 즉, 짝을 지어주지 못한 여는 괄호가 남아있어서 지금 이 문자열이 올바르지 않은 괄호 쌍임을 알 수 있게 됩니다.

 

여기까진 좋은데 그 다음 괄호로 가보겠습니다. 닫는 괄호이니 여는 괄호와 매칭을 시켜줘야 하는데 남아있는 여는 괄호가 없습니다. 즉 짝을 지어주지 못한 닫는 괄호가 남아있어서 지금 이 문자열이 올바르지 않은 괄호 쌍임을 알 수 있게 됩니다.

 

그리고 이 과정을 잘 생각해보면 가장 최근의 것이 가장 먼저 나오게 됩니다. 즉 FILO인거고 스택 자료구조를 이용해서 구현을 할 수가 있습니다. 그래서 과정을 구체적으로 정리해보면 이런 식입니다.

 

여는 괄호가 나오면 스택에 추가하고, 닫는 괄호가 나오면 스택이 비어있거나 스택의 top이 짝이 맞지 않는 괄호인지를 먼저 확인합니다. 여기서 걸리면 올바르지 않은 괄호 쌍인 거고, 짝이 맞는 괄호라면 pop을 해줍니다. 모든 과정을 끝낸 후에 스택이 비어있는지도 확인을 해줘야 합니다.

 

공백을 포함한 줄의 입력이 조금 껄끄러울 수 있는데 0x02강에서 배웠듯 getline을 이용하면 됩니다.