3015번: 오아시스 재결합

3015번: 오아시스 재결합

N개의 수들이 주어질 때, 이 중 두 개의 수(한 개의 쌍)를 고른다.

이 때 이 두 수 사이에 이 두 개의 수보다 크지 않은 수들로만 구성되는 쌍의 개수를 묻는 문제이다.

N개의 수들이 담겨져 있는 배열을 A라 할 때

앞에서부터 차례대로 A[i]를 추가함에 따라 생기는 쌍의 개수를 생각해보자.

만약에 A[i-1]이 A[i]보다 작다고 생각하자.

그럴 경우에는 앞으로 A[j](i < j)를 확인 할 때 A[i-1]과 A[j]이 쌍을 이룰 일은 절대 없다.

이 두 수 사이에 A[i-1]보다 큰 A[i]가 존재하기 때문이다.

즉 내가 A[i]를 추가하였을 때 이전의 A[i]보다 작은 수는 앞으로의 결과에 영향을 못끼친다는 것이다.

그러므로 매 상황마다 이전의 자신보다 작은 수를 제거하면서 답을 구하게 되며

이는 스택을 이용하여 편하게 구현할 수 있다.

좀 더 정확하게 매 과정에 대해서 생각해보자.

스택 s는 매번 A[i]보다 큰 수가 나올 때까지 s.pop()을 하여 제거를 할 것이다.

이 때 제거를 한 수들은 A[i]보다 작은 수이며 이들이 오름차순으로 pop()이 되기에

모두 A[i]와 쌍이 되는 것을 알 수 있다.

모두 다 제거를 완료했을 때에 s가 비어있지 않다면 이 수까지 쌍이 된다.

위의 알고리즘만으로는 이 문제의 답이 될 수 없다.

'3 3 2 2 3' 이 반례가 되는데 마지막 3을 추가하기 전 스택 s에는 '3 3 2 2'가 들어 있게 된다. (오른쪽이 top)

이 때 3을 추가하기 위하여 3보다 작은 2들이 지워지며 '3 3'가 되고 아직 s가 비어있지 않기에

두 번째 3과 다섯 번째 3까지도 쌍으로 추가 되게 되는데 이 때 첫 번째 3과 다섯 번째 3도 쌍이기 때문이다.

즉 위 알고리즘에서 간과한 부분은 수들이 같은 수가 연속적으로 나올 수 있다는 것이다.

스택을 이용하여 값을 저장해 왔지만 이제 그 값이 몇 개가 연속으로 나왔는 지에 대한 정보도 필요한 것이다.

이제 스택에 2개의 정보를 pair를 통해 집어넣으면서 위의 알고리즘을 약간 수정하면 풀 수 있는 문제이다.

놓치기 쉬운 예외가 많이 발생하는 문제였다.