[백준][17298][C++] 오큰수

링크

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

17298번: 오큰수

해설

 

오큰수란 오른쪽의 수 중에 현재 수보다 크면서 가장 왼쪽에 있는 수를 말합니다.

 

우선 이 문제를 풀기위해선 스택을 사용해야 합니다.

각 숫자들을 모두 오른쪽 숫자와 비교해가면서 하면 최대 O(N ^ 2) 가 걸리므로 비효율적입니다.

그래서 스택을 이용해서 스택에는 현재수의 오큰수 후보들이 들어있고

오른쪽에서 왼쪽으로 가면서 스택을 pop push 합니다.

 

1. 자신보다 작거나 같으면 pop합니다.

2. 자신보다 크면 멈추고 해당 숫자가 오큰수가 됩니다.

3. 만약 스택이 비었을 경우 오큰수가 없는 것이므로 -1 입니다.

4. 최종적으로 스택이 자신을 push합니다.

 

위의 조건에 따라 오큰수가 정해지게 됩니다.

왜 이런 조건들이 되는지 설명해드리겠습니다.

 

1. 자신보다 작거나 같으면 pop합니다.

우선 x번째 수 보다 작거나 같으면 왼쪽의 x-1, x-2, ... 번째 수 들은 오큰수를 구할 때 어차피 x번째 수보다

작은 수이므로 x번째 수뿐만 아니라 왼쪽의 x-1, x-2, ... 번째 수 들의 오큰수 후보가 될 수 없습니다.

고로 pop합니다.

 

위의 그림과 같이 7과 8 사이의 2 3 1 4 는 더 이상 쓸모가 없습니다.

왼쪽에서 7보다 작은 수가 나올 경우 7이 오큰수 후보가 될 것이고

7보다 큰 수가 나오면 7의 오큰수인 즉 8과 그 뒤의 수가 오큰수가 되기 때문입니다.

 

2. 자신보다 크면 멈추고 해당 숫자가 오큰수가 됩니다.

자신보다 큰 수를 찾으면 그게 오큰수 이므로 멈추고 오큰수가 됩니다.

더 뒤에 있는 수들은 굳이 작은지 비교해서 빼내지 않습니다.

왜냐면 나중에 필요할 때 검사하면 되지 굳이 미리 다 검사해둘 필요는 없습니다.

 

3. 만약 스택이 비었을 경우 오큰수가 없는 것이므로 -1 입니다.

스택이 비었다는 것은 스택 내의 모든 수가 현재수보다 작다는 것이므로 오큰수는 없습니다.

 

4. 최종적으로 스택이 자신을 push합니다.

스택에서 본인보다 작거나 같은 수를 모두 삭제했으므로 본인이 push 되어 오큰수 후보가 됩니다.

 

 

백준 예시를 사용해서 풀어보겠습니다.

 

3 5 2 7

 

맨 오른쪽부터 순서대로 스택에 쌓아보겠습니다.

 

now : 7

스택이 비어있고 오큰수는 -1

현재수를 push합니다.

NGE(4) = -1

 

now : 2

현재수보다 큰 수를 찾았으므로 멈춥니다

현재수를 push합니다.

NGE(3) = 7

 

now : 5

2는 현재수보다 작으므로 pop

7은 현재수보다 크므로 멈춥니다.

현재수를 push합니다.

NGE(2) = 7

 

now : 3

5는 현재수보다 크므로 멈춥니다.

현재수를 push합니다.

NGE(1) = 5

 

코드

#include <iostream>
#include <stack>
using namespace std;
 
stack <int> STACK;
int N;
int NUM[1000000], TABLE[1000000];
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	cin >> N;
	for (int i = 0; i < N; ++i)
		cin >> NUM[i];
 
	for (int i = N - 1; i >= 0; --i) {
		int now = NUM[i];
		while (!STACK.empty()) {
			if (STACK.top() <= now)
				STACK.pop();
			else
				break;
		}
		if (STACK.empty())
			TABLE[i] = -1;
		else
			TABLE[i] = STACK.top();
		STACK.push(now);
	}
	
	for (int i = 0; i < N; ++i) {
		cout << TABLE[i] << " ";
	}
 
	return 0;
}