CSES PS - nearest smaller values(NSV)

https://cses.fi/problemset/task/1645/

하나의 새로운 알고리즘, O(n)

카르테시안 트리라는 자료구조 구현의 기본 아이디어라고 함.

https://wcipeg.com/wiki/All_nearest_smaller_values

영어설명

 

monotonic stack이라고도 함.

https://www.acmicpc.net/problem/17298 다른 기본문제

 

<문제설명>

최대 2e5개의 숫자를 입력받으면서, 처음부터 입력받은 그 시점까지 입력받은 숫자보다 작은 수 중에 가장 가까운 값의 인덱스를 반환하라.

 

<풀이>

1. k<i<j에 대해, a[k] < a[i] 일 때만 a[k]가 훗날 마주칠 a[j]의 nsv가 될 여지가 있다.

그 외의 경우 즉, a[k] >= a[i] 인 경우 a[j]의 nsv가 될 여지가 없으므로 생각하지 않는다.

 

2. 배열을 입력받으면서 앞으로 유지해야 하는 값의 인덱스를 stack에 둔다. 그럼 스택엔 값이 증가하는 순서대로 쌓이게 된다. 

 

3. 정리하자. 입력받은 배열의 값보다 작은 값들을 오름차순으로 스택에 유지하면,  top이 바로 nsv의 인덱스이다.

 

문제가 인덱스를 반환하는거다 보니 복잡할수있지만, 값에 좀더 초점을 맞춰서 읽으면 이해될 것

 

<코드>

#include <iostream>
#include <stack>
using namespace std;
int main() {
	int n, a[200001]; cin >> n;
	stack<int> s;
	s.push(0);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		//입력받은 배열의 값보다 큰 값들은 없애버림
		while (a[s.top()] >= a[i]) s.pop();
		cout << s.top() << " ";
		s.push(i);
	}
}