16. 가장 가까운 작은 값 (Nearest smaller elements, c++)

가장 가까운 작은 값 (Nearest smaller elements)?

 

배열의 모든 요소에 대해서 앞에 있는 값들 중 가장 가까이에 위치한 작은 값을 찾는 문제입니다.

 

Stack을 이용해서 이러한 문제들을 효과적으로(O(N)) 해결할 수 있습니다.

 

왼쪽에서 오른쪽으로 배열을 탐색할 것인데, Stack을 이용해 특정 요소들을 관리할 것입니다.

 

배열의 각 인덱스에 대해서, Stack의 값과 비교해 자신보다 큰 값들을 모두 제거합니다.

 

Stack이 비어있게 되거나 Stack의 top 요소가 자신보다 작다면 제거하는 작업을 중단합니다.

 

그렇다면 Stack의 top 요소가 nearest smaller element 입니다.

 

이후 자신의 값을 Stack에 추가하고 이 작업을 반복합니다.

 

{ 1, 3, 4, 2, 5, 3 } 배열을 예로 들면 아래와 같습니다.

Stack (before)	index	index/value	Nearest smaller element	Stack (after)
{ }	1	1	-	{ 1 }
{ 1 }	2	3	1	{ 1, 3 }
{ 1, 3 }	3	4	3	{ 1, 3, 4 }
{ 1, 3, 4 }	4	2	1	{ 1, 2 }
{ 1, 2 }	5	5	2	{ 1, 2, 5 }
{ 1, 2, 5 }	6	3	2	{ 1, 2, 3 }

 

Stack에 대한 삽입과 삭제 연산은 O(1)에 수행되는 연산이므로 이 알고리즘의 성능은 배열의 길이에 달려있습니다.

 

배열의 모든 요소를 정확히 1번씩 탐색하므로 O(N)에 수행됩니다.