stack에 값과 인덱스를 같이 저장해 시간복잡도를 낮추는 것이 요점인 문제이다.
O(N), 2*N정도로 줄이는게 요점이다.
완전탐색을 하게된다면, 모든 요소에서 그 뒤에 있는 요소를 전부 검사해야 하기 때문에
1/2N^2(등차수열의 합) 의 시간이 걸리게 되어 1,000,000의 size의 입력인 경우 1초를 훨씬 초과하게 된다.
이를 줄이기 위해서 스택을 사용해야 된다.
인덱스 스택과 값 스택 두개를 사용하거나, 스택 하나에 인덱스와 값 정보를 전부 저장해 주어야 한다.
그리고 정답을 저장하는 배열을 하나 만들어 이를 전부 -1로 초기화해준다.
이는 오큰수가 없는 경우에 -1이 들어가야 하기 때문이다.
오큰수가 없는 경우를 따로 체크해 주지 않고, 오큰수가 있는 경우만 체크해 준다면 그의 여집합은 자동으로 체크가 된다.
예시를 들어 3 5 2 7 이 입력으로 들어온다고 하자.
이를 스택에 넣어줄때 {3,0}, {5,1}, {2,2}, {7,3} 을 넣어주는 방식이다.
순서대로 진행을 해보면, 처음 정답 배열에는 -1, -1, -1, -1이 들어간다.
여기서 체크하기 위한 스택에 {3,0}이 들어가고, 다음으로 넘어간다.
체크 스택 : {3, 0}
정답배열 : -1 -1 -1 -1
그 다음에는 {5,1}이 들어오고, 이것이 3보다 크기 떄문에 정답 배열에 인덱스에 접근해서 정답 배열은 5, -1, -1, -1이 된다.
그와 동시에 스택에 기록된 {3,0}은 더이상 체크할 필요가 없으므로, pop을 해준다.
체크 스택 : {5, 1}
정답배열 : 5 -1 -1 -1
그 다음에는 {2, 2}가 들어온다. 2는 5보다 작기때문에 따로 체크를 해주지 않는다.
체크 스택 : {5, 1}, {2, 2}
정답배열 : 5 -1 -1 -1
그 다음에는 {7, 3}이 들어온다. 그러면서 스택의 top을 계속 비교하면서 pop을 해주면 된다.
2보다 7이 크기 때문에 이에 따라 정답 배열을 바꿔주고,
다시 또 5보다 7이 크기 때문에 이에 따라 다시 바꿔준다.
그러면 스택이 비어버리기 때문에
체크 스택 :
정답배열 : 5 7 7 -1
결론적으로 마지막 요소 빼고 나머지 요소가 전부 오큰수가 있을때가 최악의 경우가 되고, 이때 시간은 2 * N 이 된다.
따라서 완전탐색시에는 N^2가 되지만, 스택을 사용한다면 N time에 문제를 풀 수 있다.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
int N;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>N;
vector<pair<int,int>>v;
vector<int>ans(N, -1);
for(int i=0; i<N; i++){
int input;
cin>>input;
if(v.empty()){
v.push_back({input,i});
}else{
while(v.back().first < input && !v.empty()){
ans[v.back().second] = input;
v.pop_back();
}
v.push_back({input, i});
}
}
for(auto e : ans)
cout<<e<<' ';
}