백준 17298 오큰수 C++ (Stack)

문제

www.acmicpc.net/problem/17298

17298번: 오큰수

코드1 (값을 이용하여 <- 방향으로 순회)

#include <bits/stdc++.h>

using namespace std;

int n, arr[1000001], ans[1000001];
stack<int> s;

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

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	for (int i = n - 1; i >= 0; i--)
	{
		while (s.empty() == false && s.top() <= arr[i])
			s.pop();

		if (s.empty())
			ans[i] = -1;
		else
			ans[i] = s.top();

		s.push(arr[i]);
	}

	for (int i = 0; i < n; i++)
	{
		cout << ans[i] << " ";
	}
	
	return 0;
}

 

코드2 (인덱스를 이용하여 <- 방향으로 순회)

#include <bits/stdc++.h>

using namespace std;

int n, arr[1000001], ans[1000001];
stack<int> s;

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

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	for (int i = n - 1; i >= 0; i--)
	{
		while (s.empty() == false && s.top() <= arr[i])
			s.pop();

		if (s.empty())
			ans[i] = -1;
		else
			ans[i] = s.top();

		s.push(arr[i]);
	}

	for (int i = 0; i < n; i++)
	{
		cout << ans[i] << " ";
	}
	
	return 0;
}

 

코드3 (인덱스를 이용하여 -> 방향으로 순회)

#include<bits/stdc++.h>

using namespace std;

int n, arr[1000004], ans[1000004];
stack<int> s;

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

	cin >> n;
	fill(ans, ans + 1000004, -1);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		while (s.size() && arr[s.top()] < arr[i])
		{
			ans[s.top()] = arr[i];
			s.pop();
		}

		s.push(i);
	}

	for (int i = 0; i < n; i++)
	{
		cout << ans[i] << " ";
	}
	
	return 0;
}