[백준 BoJ] 17298 - 오큰수

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
int arr[1000001];
stack<int> s1;
stack<int> s2;
stack<int> ms;

void clear() {
	while (!s1.empty()) s1.pop();
	while (!s2.empty()) {
		s1.push(s2.top());
		s2.pop();
	}
}
int empty_check() {
	int Max = 0;
	if (!ms.empty())Max = ms.top();
	
	while(!ms.empty()) ms.pop();
	
	return Max;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int N;
	

	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		s1.push(num);
		arr[i] = num;
	}

	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			int num = s1.top();

			if (arr[i] < num) {
				ms.push(num);
			}
			s2.push(num);
			s1.pop();
		}

		int Max = empty_check();

		if (!Max) cout << "-1 ";
		else cout << Max << " ";
		
		clear();
	}
}

처음에 위와 같이 작성했다가 시간초과가 떴다...

 

다른 방법이 생각이 떠오르질 않아 다른 사람의 코드를 참고했다.

// https://www.acmicpc.net/problem/17298
// 오큰수
#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int N;

	cin >> N;
	stack<int> s;
	vector<int> v;
	vector<int> ans(N, -1);

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}
	bool flag = false;
	for (int i = 0; i < N; i++) {
		while (!s.empty() && v[s.top()] < v[i]) {
			ans[s.top()] = v[i];
			s.pop();
		}
		s.push(i);
	}

	for (auto a : ans) cout << a << " ";
}

for문이 돌 때마다 인덱스를 스택에 저장하여 해당 인덱스를 사용해 값을 비교하는 방식이다. 인덱스를 사용하지 않는 벡터는 모두 -1로 초기화 되어 있다.

 

참고 : https://vansoft1215.tistory.com/109?category=491027