[PS] 스택 자료 구조를 사용하는 게 효과적인 상황

오늘 백준 17298 '오큰수' 문제를 풀면서 드디어(..!) 스택 자료 구조를 사용해야 하는 상황임을 알 수 있는 직관을 얻을 수 있었다. 재귀, dynamic programming에서 이런 직관을 얻고, PS 역량이 약간 올라갔다고 체감했던 터라 기분 좋은 깨달음이었다.

스택 자료 구조는 양파 껍질 같은 상황에서 쓰인다.

백준 9012 '괄호'

정글 과정 중 코치님께서 하신 말씀이다. 그때 당시에는 백준 9012 '괄호'와 같은 문제를 풀면서 어렴풋이 '문제가 양파 같긴 하다' 정도로 생각하고 끝났다. 그런데 사실은 더 큰 뜻이 있었다.

양파 '껍질'이라, 양파 안은 관심이 없다!

9012 '괄호' 문제와 같이 올바르게 괄호가 닫혔는지 확인할 때를 가정한다. (()(())) 이 case의 경우 가장 마지막에 빨간색 ')'으로 닫히며 올바르게 괄호가 닫혔다고 판단하게 된다. 이 과정을 순서대로 작성하면 아래와 같다.

1. 주어진 괄호들의 가장 왼쪽에서 부터 순회한다.
2. 여는 괄호는 스택에 넣는다(push).
3. 닫는 괄호가 오면 스택의 가장 상단의 것과 한 쌍을 이루는지 확인한다.
4. 한 쌍을 이루면 정상, 이루지 못 하면 비정상으로 판단한다.

3번 과정에서 빨강 글씨의 괄호가 (()(())) 이 괄호들 중 빨강색에 해당한다. 즉, 3번의 판단 과정에는 빨강 괄호 속에 포함된 검정에 대한 판단이 없다. '(양파) 안은 모르겠고~ 이 괄호 적절해? 안 해?'와 같은 상황이다.

 

또 달리 이를 이해하면, 검정 괄호 부분이 어떤 형태이든 두 빨강 괄호가 정상인지 판단하는 과정(메커니즘)이 항상 동일하다. 이럴 때 스택 자료 구조를 사용한다!

양파 안에는 또 양파 '껍질'이 있다.

까도 까도 나오는 게 양파인 것처럼 껍질이 품는 내부에는 또 껍질이 있다. 앞서 봤던 (()(())) 이 case를 다시 한 번 보자. 위 순서의 1번 과정에서 인덱스 1 순서라고 생각하면 스택에 (( 이 담겨 있을 것이다.

 

검은색 괄호는 빨간색 괄호에 영향을 받을까? 전혀 안 받는다! 양파 껍질 안의 또 다른 양파 껍질은 별개의 일인 것이다. '내 앞에 어떤 놈이 왔었든지 간에 나는 내 조건에 맞는 '한 녀석'과만 만나면 된다.'

 

또 달리 이를 이해하면, 검정 괄호 바깥 부분이 어떤 형태이든 검정 괄호가 정상인지 판단하는 과정(메커니즘)이 항상 동일하다. 이럴 때 스택 자료 구조를 사용한다! 이렇게 9012 '괄호' 문제를 이해하고 아래 문제를 보자.

boj.ma/17298/t og:image

나보다 오른쪽에 있는 나보다 작은 수에 관심이 없다.

7, 6, 3, 4, 3, 8의 수열에서 빨강색 글씨인 7은 자기 뒤에 6이 오든 1이 오든 영향을 받지 않는다. 즉, 빨간색 내부의 검은색 부분이 어떤 형태든 상관없다. '(양파) 안은 모르겠고~ 이 숫자 적절해? 안 해?'와 같은 상황이다.

나보다 오른쪽에 있는 수는 또 다른 양파 '껍질'이다.

7, 6, 3, 4, 3, 8 수열을 순회하는 과정에서 인덱스 1 순서라고 생각하면 스택에는 7, 6이 담겨 있을 것이다. 검정색 숫자는 빨간색 숫자에 영향을 받는가? 전혀 안 받는다. 즉, '내 앞에 어떤 놈이 왔었든지 간에 나는 내 조건에 맞는 '한 녀석'과만 만나면 된다.'에 해당한다.

 

여기서 조건은 '오큰수' 문제에서는 '나보다 더 큰지?'였고, 괄호 문제에서는 '나와 쌍을 이루는지?'였다. 두 문제가 일맥상통함을 알 수 있다.

 

우리는 아와 같은 상황에서 직관적으로 스택 자료 구조를 떠올리면 되는 것이다.

1. '안은 모르겠고~ 이거 적절해? 안 해?'
2. '내 앞에 어떤 녀석이 왔든지 간에 나는 내 조건에 맞는 '한 녀석'과만 만나면 된다.'

---