[C++] 오큰수 - 17298

17298번: 오큰수

 

출력해야 하는 수의 조건

1. 현재 위치보다 오른쪽에 있어야함

2. 현재 위치의 수보다 커야함

3. 1,2번 조건에 만족하며 가장 왼쪽에 있어야 함

4. 위의 조건에 해당하는 수가 없으면 -1을 출력

 

문제 해결법

3

5

2

7

위와 같은 예제가 주어졌을때

0번 index부터 시작하는 것이 아니라 3번 index 부터 시작합니다.

---

3번 index

-1

3번 index의 수는 가장 끝에 있는 수이기에 정답지에 -1을 기입하며

stack에 3번 index에 있는 7을 넣어줍니다.

---

2번 index

7

-1

2번 인덱스의 있는 수와 stack의 top과 비교하여 top이 더 크다면 답지에 stack.top을 넣어주고

stack에 2번 인덱스의 수을 넣어줍니다.

---

1번 index

7

7

-1

 

1번 인덱스의 수가 stack의 top(2)보다 크기 때문에 pop을 해주고

1번 인덱스 보다 큰 수인 7이 top으로 올아왔기 때문에 답지에 7을 기입해줍니다.

stack에는 1번 인덱스의 수(5)를 넣어줍니다.

 

---

0번 index

5

7

7

-1

0번 인덱스의 수와 stack의 top(5)와 비교

5가 더 크기 때문에 답지에 5를 기입하고 3을 넣어줌

 

#include<iostream>
#include <vector>
#include<stack>
using namespace std;

int N;
stack<int> s;
vector<int> v, ans;

int main()
{
	cin >> N;
	v.resize(N, 0);
	ans.resize(N, 0);

	for (int i = 0; i < N; i++)
		cin >> v[i];

	for (int i = N - 1; i >= 0; i--)
	{
		while (!s.empty() && s.top() <= v[i])
			s.pop();

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

		s.push(v[i]);
	}

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