[BOJ] 17298번_오큰수_스택 (C++)

[문제]

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

크기가 N인 수열에서 각 원소에 대해서 오큰수를 구하는 문제이다.
*오큰수란? 해당원소보다 오른쪽에 있으면서 큰 수 중에서 가장 왼ㅉ고에 있는 수를 의미한다.
오큰수가 없다면 오큰수는 -1로 한다.

[사용 알고리즘]

스택

[풀이 핵심]

• 각 원소의 index를 stack에 저장해가며 해결하는 것이 좋다.
• stack이 비어 있거나, 현재 index의 원소값( A[i] )이 stack의 top의 원소값( A[s.top()] )보다 작거나 같다면, 다음 원소와 비교를 해야하므로 stack에 현재 index를 push해준다.
• 현재 index의 원소값이 stack의 top보다 크다면, 현재 index의 원소값이 stack의 top의 원소값의 오큰수가 된다. 따라서 A[s.top()] = A[i]를 통해 오큰수를 저장해준다. 그리고 s.top()의 오큰수를 구했으니 s.pop()을 해준다.
• 마지막까지 스택에 남아있는 인덱스는 오큰수가 없는 것이므로 -1로 초기화해준다.
• A에 저장한 오큰수를 전부 출력한다.

[코드]

//boj17298번_오큰수_자료구조(스택)

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

using namespace std;

int main() {
	int N;
	cin >> N;

	vector<int> A;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		A.push_back(num);
	}

	stack<int> s;

	for (int i = 0; i < N; i++) {
		while (true) {
			if (s.empty() || A[s.top()] >= A[i]) {
				s.push(i);
				break;
			}

			if (A[s.top()] < A[i]) {
				A[s.top()] = A[i];
				s.pop();
			}
		}

	}

	while (!s.empty()) {
		A[s.top()] = -1;
		s.pop();
	}

	for (int i = 0; i < A.size(); i++) {
		cout << A[i] << " ";
	}

	return 0;
}