[baekjoon 17298] 오큰수 (스택) (C++)

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

17298번: 오큰수

현재 수의 오른쪽에 있는 수 들 중 나보다 큰 가장 왼쪽의 수를 출력하는 문제이다.

 

즉, 1 9 8 10 이면 1의 오큰수는 9(큰 수 중 바로 왼쪽), 9의 오큰수는 10, 8의 오큰수는 10, 10의 오큰수는 없기에 -1을 출력하면 된다.

 

또한 입력값의 범위는 백만으로, 매 수마다 오른쪽 범위로 반복문을 돌려서 나보다 큰 수를 찾는 2중 for문을 이용하면 시간 초과가 날 것이다.

따라서, 스택 자료구조를 이용해서 매번 검사하지 말고 오큰수를 찾지 못한 수들을 스택에 넣어두다가 만약 스택의 top보다 큰 수가 등장하면 모아두었던 수들의 오큰수로 지정해주면 된다.

 

위의 전략에 따르면

1 2 3 4 5 6 7 8 9인 경우는 수가 쌓이지 않고 바로바로 pop 되면서 오큰수를 찾을 수 있을 것이다.

9 8 7 6 5 4 3 2 1의 경우는 스택에 9 8 7 6 5 4 3 2 1이 쌓이고, top보다 큰 수가 한 번도 등장하지 않기 때문에 모두 -1이 될 것이다.

 

만약 top만 보고 top보다 큰 수가 등장하면 스택을 pop 하면서 오큰수를 찾게 되는데, 만약에 top보다 큰 수가 있다면 어떻게 될까?

a가 저장되어 있고 b가 c를 만난 상황이라고 가정해보자.

(a > b이고 b < c이다, 즉 a와 c의 대소 관계는 알 수 없다.)

그렇다면 a 앞까지 pop 되면서 a + 1 ~ b의 인덱스까지 c가 오큰수로 저장될 것이고, a는 계속 스택에 남아있는다.

이후 나중에 c'를 만나서 이 로직이 실행될 때 a보다 c'가 크다면 a의 오큰수는 c'이 되는 것이고, 아니면 -1이 될 것이다.

 

#include <iostream>
#include <stack>

using namespace std;

int n, arr[1000001], record[1000001];
stack<int> st;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		record[i] = -1; // 미리 -1을 저장
	}

	st.push(0); // 첫 번째 인덱스를 미리 저장

	for (int i = 1; i < n; i++) { 인덱스 1부터 n-1까지
		while (!st.empty() && arr[st.top()] < arr[i]) { // 만약 top이 cur보다 작다면 cur이 오큰수
			record[st.top()] = arr[i]; // 스택에 쌓아뒀던 수들의 오큰수를 arr[i]로 저장해주자
			st.pop();
		}
		st.push(i);
	}
	for (int i = 0; i < n; i++) {
		cout<<record[i]<<" "; // 오큰수를 찾지 못한 수들은 자연스럽게 -1을 출력
	}
}