[백준] 17298번 오큰수 C++ 코드

코드

#include <iostream>
#include <stack>

using namespace std;
stack<int> st; // 오큰수를 찾을 스택
stack<int> answer; // 정답을 넣어줄 스택
int n, a[1000003];

void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main() {
	FASTIO();
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = n - 1; i > -1; i--) {
		// top을 검사하면서 top보다 작은 경우를 탐색
        while (st.size()) {
			int top = st.top();
			if (top > a[i]) break;
			st.pop();
		}
		// 만약 오큰수를 찾는 스택이 비어있다면 -1을 스택 정답에 넣어줌
		if (st.empty()) {
			answer.push(-1);
		}
        // 오큰수를 찾았다면 해당 값을 정답 스택에 넣어줌
		else {
			answer.push(st.top());
		}
        // 오큰수 스택에 넣어준다 (다음 탐색을 위해)
		st.push(a[i]);
	}
    // 정답 출력
	while (answer.size()) {
		cout << answer.top() << " ";
		answer.pop();
	}
	cout << '\n';
	return 0;
}

풀이

오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 수열의 크기가 최대 100만이므로, O(N)으로 해결할 생각을 해야한다. 이를 위해 떠올린 자료구조는 stack이다. 뒤에서부터 검사하면서, 스택이 비어있다면 -1, 스택의 꼭대기보다 Ai가 작다면 스택 꼭대기에 있는 값을 정답에 넣어주고, 다음 탐색을 위해 Ai를 오큰수 스택에 넣어준다.

 

스택은 후입선출 자료구조이다. 따라서 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 찾기 용이하다. 왜냐하면 가장 왼쪽에 있는 수는 스택의 꼭대기에 존재하기 때문이다. 스택이 비어있다면 해당 수보다 큰 값이 오른쪽에 없다는 뜻이 되므로 -1을 넣어주면 된다.