[실전 알고리즘] 0x04강 - 스택 1(수식의 괄호 쌍)_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍)에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

저번 강의에서 예고한 대로 스택의 응용 사례 중 첫 번째인 수식의 괄호 쌍을 다뤄보겠습니다.

 

 

수식의 괄호 쌍 문제는 주어진 수식의 괄호 쌍이 올바른지 판단하는 문제입니다. 편의상 수식은 제외하고 괄호 쌍만 생각해봅시다.

 

초중고 12년, 그리고 대학 n년간의 짬으로 직접 눈으로 관찰하기만 해도 그냥저냥 올바른지 아닌지 판단을 할 수 있긴 합니다. 그런데 이 문제를 어떻게 컴퓨터로 해결할 수 있을까요? 놀랍게도 이 문제는 스택으로 $O(N)$에 해결할 수 있습니다. 코딩테스트에 꼭 나온다고 장담할 수 있는 문제는 아니지만 잊을만하면 형태를 살짝 바꾸거나, 조금 응용해서 잘 나오는 문제입니다.

 

일단 문제 해결을 위한 관찰을 몇 가지 해봅시다. 우리가 이 문제를 보고 머릿속에서 푸는 과정을 잘 끄집어내어 명료하게 정리를 해야 합니다. 다음 슬라이드로 넘어가기 전에 적혀있는 저 문자열이 올바른 문자열인지 아닌지 어떻게 판단할 것인가 충분히 고민해보세요.

 

일단 ( 와 ) 의 갯수를 세볼 것입니다. 둘의 갯수가 다르면 올바르지 않은 문자열일테니까요. 그러나 둘의 갯수가 같다고 해서 꼭 올바른 문자열인건 아닙니다. ) ( 처럼요. 만약 관찰력이 뛰어나시다면 모든 순간에 ) 의 갯수가 ( 의 갯수를 넘지 않으면 된다는 사실을 알아차리셨을 수도 있겠습니다.

 

이외에 붙어있는 ( ) 를 계속 지웠을 때 문자열을 모두 없앨 수 있는지를 확인하는 방법도 있습니다.

 

괄호가 한 종류일 때에는 갯수를 세는 방법으로 해결할 수가 었는데 여러 종류일 때는 그렇지 않습니다. 저기 적힌 예시를 갯수를 세는 방식으로 처리할 수 있을까요?

 

반면 붙어있는 ( ) 혹은 { } 를 지우는 방법은 여전히 잘 동작합니다. 이 방법을 배열로 구현할 경우 최대 $N/2$번 중간에 있는 원소의 삭제가 발생하기 때문에 $O(N^2)$이고 연결 리스트로 구현할 경우 $O(N)$입니다. 연결 리스트로 구현을 하는게 엄청 어려운건 아닙니다. 연결 리스트 연습용으로 한 번 짜보셔도 괜찮아요. 그렇지만 스택을 이용하면 조금 더 간단하게 할 수 있습니다. 이 방법을 고안하기 위해서는 하나의 관찰이 추가로 더 필요합니다.

 

그 관찰은 바로 닫는 괄호는 가장 최근에 들어온 여는 괄호를 없애버리는 명령이라고 생각해도 된다는 것입니다. 예시를 살펴봅시다.

 

이 문자열에 대해 처리를 해보겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

처리 과정이 이해가 가나요? 그리고 처리하는 과정을 살펴볼 때 떠오른 자료구조가 없었나요? 원소를 뒤에서 계속 삽입/삭제 하는 것, 가장 최근의 것이 가장 먼저 나오는 자료구조, 즉 스택입니다.

 

여는 괄호가 나오면 스택에 넣습니다. 닫는 괄호가 나오면 우선 스택이 비어있는지를 확인합니다. 스택이 비어있으면 잘못된 괄호 문자열입니다. 만약 스택이 비어있지 않지만 스택의 top이 짝이 맞지 않는 괄호인 경우에도 잘못된 괄호 문자열입니다. 짝이 맞을 경우엔 pop을 합니다.

 

모든 과정이 끝난 뒤에 스택에 문자열이 남아있는지도 확인해야 합니다.

 

BOJ 9012번 : 괄호 문제의 정답 코드를 참고하세요. 원래 9012번은 ( )만 있을 때에 대한 문제이나 이해를 돕기 위해 정답 코드는 { }가 같이 있을 때도 처리할 수 있도록 짜두었습니다.

 

괄호쌍 문제는 이렇게 해결이 되었습니다. 사실 코딩테스트에 괄호쌍 문제가 그대로 나올 확률은 거의 없습니다. 너무 유명한 문제여서요. 그렇기에 괄호쌍 문제와 관련해서 몇 가지의 응용 문제에 대한 간단한 접근법을 알려드리려고 합니다. 문제는 그룹 내의 문제집에서 확인할 수 있으니 혼자 힘으로 먼저 도전해보고 싶으신 분들은 뒤의 내용을 더 이상 읽지 마세요.

 

BOJ 10799번 : 쇠막대기 문제입니다. 일단 괄호쌍을 볼 때 지금 보고 있는 이 닫힌 괄호가 레이저를 의미하는지 쇠막대기를 의미하는지는 그 앞의 괄호를 보면 알 수 있습니다. 레이저를 쏠 때 몇 개의 막대기가 잘려나가는지를 어떻게 알 수 있을지, 쏘는 그 순간에 스택의 길이와 연관지어서 생각해보세요.

 

BOJ 2504번 : 괄호의 값 문제입니다. 일단 사람 손으로 문제를 풀어봅시다. 그 과정을 어떻게 스택 상에서 처리하면 될지도 먼저 생각을 해봅시다. 하다보면 스택에서 단순히 문자만 가지고 있는게 아니라, 값도 가지고 있어야 한다는 사실을 알 수 있습니다.

 

닫힌 괄호를 만나 스택에서 pop을 할 때, 값도 꺼내서 뭔가 처리를 한 뒤 어딘가에 그 값을 넣어줘야 합니다.

 

BOJ 2493번 : 탑 문제입니다. 이 문제는 괄호쌍과는 관련이 없는 스택 응용 문제입니다. 문제를 보면 각 탑에 대해 나보다 높은 탑 중에서 왼쪽으로 가장 가까이 있는 탑을 찾아야 합니다.

 

2 3 4 6 5 1이 있을 때 2 3 4는 6이 나온 이후로 절대 레이저 신호를 수신할 일이 없다는 것을 알 수 있습니다. 즉 2 3 4는 6이 나오고 나면 그냥 제거해버려도 된다는 것이죠. 그러면 "레이저 신호를 수신할 가능성이 있는 탑"의 리스트를 가지고 있다고 할 때 그 리스트는 내림차순일 것입니다.

 

새로운 탑의 높이를 볼 때 그 탑을 리스트에 어떻게 적절하게 넣을 수 있을까 고민해보세요.

 

이번 강의에서는 스택의 괄호 쌍 문제와 스택을 응용한 문제들에 대해 살펴보았습니다.

 

접근법을 보고 풀었든, 그렇지 않든 제시된 응용 문제 3개를 모두 풀어낼 수 있다면 스택과 관련한 코딩테스트 문제에서 어려움을 겪을 일은 없을 겁니다. 이것보다 더 어렵게 나오면 어차피 거의 대부분의 사람이 못풀어요.

 

응용 문제의 풀이가 잘 이해가 안 간다고 해서 너무 스트레스 받지 마세요. 처음 접했으면 어려운게 당연한거에요. 다른 것들을 먼저 공부하고 다시 보면 한결 나을겁니다. 질문 있으면 편하게 질문해주세요.