투포인터 응용

가령 상황을 하나 혹은 두 개의 배열로 나타낼 수 있다고 하자.

 

배열이 하나라면, index 0부터 최댓값을 담는 배열을 만들고,

 

가장 끝 index부터 최댓값을 담는 배열을 만들고, 상황에 맞게 사용하는 것이다.

 

꼭 최댓값이 아니더라도, 한쪽에서는 최대, 다른 한쪽에서는 최소를 잡을 수도 있겠다.

 

 

이런 유사한 방식을 세번 이상 사용한 것 같다. 아마 다른 사람이 보면 이게 무슨 말인가 싶겠지만,

 

일단 내가 기억하고자 하는 목적으로 정리를 해두겠다.

 

#define ll long long
#include<iostream>
#include<vector>
using namespace std;

ll lmax[300001], rmin[300001];
int solution(vector<int> &T) {
	ll Max = T[0];
	for (int i = 0; i < T.size(); i++) {
		if (T[i] > Max)
			Max = T[i];
		lmax[i] = Max;
	}

	ll Min = T.at(T.size() - 1);
	for (int i = T.size() - 1; i >= 0; i--) {
		if (T[i] < Min)
			Min = T[i];
		rmin[i] = Min;
	}

	for (int i = 0; i < T.size() - 1; i++) {
		if (lmax[i] < rmin[i + 1]) {
			//len = i + 1;
			return i + 1;
		}
	}
}
int main(void) {
	vector<int> vec{ -5, -5, -5, -42, 6, 12 };
	solution(vec);
	return 0;
}

 

주어진 배열에서, 조건에 따라 부분 배열을 찾는 문제이다. vec 벡터를 두 개의 벡터로 나눌 것인데, 하나의 벡터의 모든 성분이 또 다른 벡터의 어떤 성분보다도 작도록 벡터를 양분하려고 할 때, 위와 같은 방법을 사용할 수 있다.