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

문제 출처

풀이

이 문제를 보고 자료구조 문제라는 것은 짐작하였다. 처음에 했던 생각은 뒤에서부터 탐색을 시작하는 것이었다. 마지막 인덱스(N-1)의 오큰수는 당연히 -1 이고 N-2를 탐색할 때 N-1이랑 비교해서 자리를 위치를 알맞게 조정하는 것을 생각하였었다. 하지만, 위치를 알맞게 삽입, 조정하는 과정에서 드는 연산량이 너무 많이 들 것이라 생각하여 바로 폐기하게 되었다. 그 다음에 들었던 생각이 stack이었다. 먼저 A[0]을 stack에 집어 넣는다. 그 다음 수, 즉 A[1]이 A[0]보다 크다면 A[0]은 그대로 pop되고 A[1]을 result 배열 해당 index(0)에 저장한다. 만약 A[1]이 A[0]보다 크지 않다면 그대로 stack에 들어오게 된다. 일반화 하면 다음과 같다.

1. A[i+1]이 A[i]보다 크다면 result[i]에 A[i+1]을 저장한다.
2. 그 다음 stack을 pop하고 새로운 top과 A[i+1]을 비교한다.
3. 마찬가지로 A[i+1]이 더 크다면 새로운 top의 인덱스에 해당하는 result배열에 A[i+1]을 저장한다.
4. 3의 과정을 stack이 비어있거나, top의 값이 A[i+1]보다 크다는 조건을 만족할 때까지 반복한다.
5. stack에 존재하는 원소는 top으로부터 바닥까지 오름차순이다.

전체 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

typedef pair<int, int> ii;


int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	vector<int> A(N);
	vector<int> result(N, -1);
	for ( int i = 0; i < N; i++ ) {
		cin >> A[i];
	}
	stack<ii> st;
	st.push(ii{ 0,A[0] });
	for ( int i = 1; i < N; i++ ) {
		while ( !st.empty() && st.top().second < A[i] ) {
			result[st.top().first] = A[i];
			st.pop();
		}
		st.push(ii{ i,A[i] });
	}
	for(int i = 0; i < N; i++){
		cout << result[i] << " ";
	}
	cout << endl;

	return 0;
}