[C++]17298_오큰수

 

 

입력 받은 값이 이전에 입력 받은 값보다 클 때가지 오큰수를 구한다.

스택 구조를 이용해 이미 오큰 수가 존재하는 인덱스에는 접근하지 않도록 한다.

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000005
int n;
int arr[MAX],ret[MAX];
stack<int> s;

int main() {
	cin >> n;
	memset(ret,-1,sizeof(int)*n);
	for(int i=0;i<n;i++){
		cin >> arr[i];
		while (s.size() && arr[s.top()] < arr[i]) {
			ret[s.top()] = arr[i]; s.pop();
		}
		s.push(i);
	}
		
		for(int i=0;i<n;i++)cout << ret[i]<<" ";
}

 

---

 

-시간 초과가 난 코드 

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000005
int n;
int arr[MAX],dp[MAX];

int main(void){
	cin >>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	memset(dp,-1,sizeof(int)*n);
	
	
	for(int i=n-2;i>=0;i--){
		for(int j=i+1;j<n;j++){
			if(arr[i]<arr[j]){dp[i]=arr[j];break;}
			else if(arr[i]<dp[j]){dp[i]=dp[j];break;}
		}
	}
	
	for(int i=0;i<n;i++)
		cout <<dp[i]<<" ";
	return 0;
}

스택을 사용하지 않을 때에 비해 이미 오큰수가 구해져 있는 값들도 중복해서 접근하면서 시간 초과가 났다.