증가하는 세개의 인덱스를 O(N)에 찾기
아예 랜덤하게 하나씩 뽑는것도 재밌을 듯. 그리고 나오는게 현재 인덱스들과 어떻게 구성되는지 비교하고 맞출 수 있으면 리턴.
아니면 앞에서부터 순회해야겠지.
현재 처음이야. 다음게 더 작아. 그럼 그걸 처음으로 잡아. 다음게 더 커. 그러면 그게 다음꺼야. 그리고 작은게 나오면 .. 이런식으로는 서로 떨어진 경우를 찾을 수 없다.
자명한 해는 소팅하는 방법.. O(NlogN)
랜덤하게 하나를 뽑는다.
5 9 이렇게 두개 뽑았는데 중간의 더 작은값이면 버리고.. 아 근데 이것도 결국에는 그걸 못찾고 지나치겠다.
해싱이 답인거같다 O(N) 뽑으려면
해싱해가면서 수를 기록한다.
아니면 프리프로세싱..!!
어 프리프로세싱 되겠다.
오른쪽에 자신보다 큰게 있는가?
왼쪽에 자신보다 작은게 있는가?
== 왼쪽의 max가 자신보다 큰가?
== 오른쪽의 min이 자신보다 작은가?
3 2 5 4 1
x x o o x
o o o o x
oo인 점이 있으니 true. 아마 두번째 프로세싱 만들면서 바로 발견가능할듯 .. !!!
아 근데 이렇게도 생각가능한데. 저런게 단 한개도 없다는 뜻은, 무조건 단조감소한다는 뜻이잖아.
..!! 띠용 !!
아 근데 "인덱스"를 찾아야 해서, 결국에는 위 방법이 될듯. 안된다는거는 확인해도 되면 그 점을 찾기는 쉽지 않아서 .. !!
vector<int> findthree(vector<int> & data){
// error cases
if(data.size()<3) return vector<int>();
// make preprocess array
vector<int> maxbuffer(data.size(),-1);
int max = data[0];
for(int i = 1; i < data.size() ; i++){
if(max<data[i]) max = data[i];
maxbuffer[i] = max;
}
// go through to track min and return
int min = data[data.size()-1];
for(int i = data.size()-2; i>= 0 ; i--){
if(min>data[i]) min = data[i];
// check if terminates
if(maxbuffer[i]<data[i]&&data[i]<min){
vector<int> ret = {maxbuffer[i], data[i], min};
return ret;
}
}
// not exist
return vector<int> ();
}
time complexity : O(N)
space complexity : O(N)
--