[BOJ] 17298 오큰수 (C++)

1. 문제 링크

https://www.acmicpc.net/problem/17298

 

2. 문제 접근

- 왼쪽에서 오른쪽으로 볼때, 자신보다 큰 수 중에서 가장 가까운(왼쪽에 있는 수)를 구하면 된다.

- 어떤 수를 기준으로 자신보다 큰 수가 등장했다는 건 그 수의 정답이 확정된다.

- 즉, 큰 값이 나타날때까지 stack에 넣어주고 대기한다. 자신보다 큰 수가 등장하면 그 수가 정답이 된다.

- 3을 처음 넣을때는 아무것도 없으므로, 바로 넣어준다. 이후 들어오는 값인 5는 스택에 있던 값인 3보다 크므로 오큰수다.

- 이에 따라서, 3을 빼주고, 3에 대한 오큰수는 5임을 알 수 있다.

 

- 2의 경우는 5에 대한 오큰수가 될 수 없기 때문에 그대로 넣는다.

- 마지막으로 들어오는 7은 2보다 크기 때문에 2의 오큰수가 성립하므로, stack에서 빼준다.

- 7은 5보다 더 크기 때문에 5의 오큰수가 성립하므로, stack에서 빼준다.

 

3. 문제 풀이

- stack이 비어있는 경우엔 그냥 넣는다.

- stack에 있는 수보다 현재 넣으려는 수가 크다면, 그 안에 있는 수들은 모두 pop 한다.

- pop되는 값의 오큰수는 결정되기 때문에 이를 바로 출력해주거나, 해당 수의 인덱스에 해당하는 값에 답을 적어준다.

- 마지막까지 스택에 남아있는 답이 존재했다면, 그 수는 오큰수가 없으므로 -1을 적어주면 된다.

- 본인의 경우 이 문제를 풀때, 스택을 pair<int,int> 형태로 만들어서 값과 인덱스 값을 같이 넣어서 처리했다.

 

 

4. 소스 코드(C++)

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
int value[1000005];
int answer[1000005];
stack <pair<int,int>> stk;
int main(void)
{
	int n;
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> value[i];
	}
	for (int i = 1; i <= n; i++)
	{
		while (!stk.empty() && stk.top().first < value[i]) // 나보다 큰 수가 등장했다면, 그 수는 나의 오큰수이다.
		{
			answer[stk.top().second] = value[i]; // 해당 인덱스의 오큰수로 갱신.
			stk.pop(); // 스택에서 꺼낸다.
		}
		stk.push({ value[i], i }); // 해당값은 스택에 넣는다.
	}
	while (!stk.empty()) // 끝까지 탐색 후 오큰수를 찾지 못했다면 모두 -1로 갱신.
	{
		answer[stk.top().second] = -1;
		stk.pop();
	}
	for (int i = 1; i <= n; i++)
	{
		cout << answer[i] << " ";
	}

}