[210614][백준/BOJ] 17298번 오큰수

문제

입출력

풀이

오큰수는 자신보다 오른쪽에 위치하면서 자신보다 큰 수 중에 가장 왼쪽에 있는 수를 의미한다.
오큰수를 찾기 위해서는 자신의 값과 앞으로 나올 수들을 비교해야하는데 이는 스택을 이용하면 된다.

1. vector v에 입력받은 값을 넣는다.
2. vector ans에 각 수에 대한 오큰수를 넣는다. 오큰수가 없는 경우에는 -1을 출력해야 함으로 기본값을 -1로 초기화한다.
3. 스택이 비어있다면 스택 s에 vector v에 대한 인덱스값을 넣는다.
4. 스택이 비어있지 않을때 현재 값이 스택의 top보다 크면 오큰수는 현재 값이 되며 pop을 해준다.
5. 배열의 길이만큼 반복한다.

코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	vector<int> V(n), ans(n, -1);
	stack <int> S;

	for (int i = 0; i < n; ++i)
		cin >> V[i];

	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 (int i = 0; i < n; ++i) 
		cout << ans[i] << ' ';
}