백준 17298번 오큰수 - 스택

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

 

풀이 참조: https://unialgames.tistory.com/entry/beakjoonproblem17298

[Baekjoon(백준)][17298번] 오큰수(C++)

 

아이디어:

1. 스택에는 "인덱스"를 넣는다.

2. 현재 수열 A[i]와 정답 수열 (나중에 출력할 수열) answer[i]를 vector로 정의한다.

3. 스택에 넣는 인덱스는 "아직 오큰수를 찾지 못한 인덱스"를 넣는다.

 

4. 최초 (0번째)에는 자연스럽게 인덱스를 스택에 push한다.

5. 스택이 비어있지않고, 스택 top의 숫자(A[myStack.top()])가 현재 수열 숫자(A[i])보다 작다면 (= 오큰수를 찾았다면)

정답 수열 answer에 입력한다.

이때, 정답 수열의 인덱스는 스택의 top에 해당하는 인덱스이다. (해당 인덱스의 오큰수를 찾았으므로)

answer[myStack.top()] = A[i]

스택에서 "오큰수를 찾은" 인덱스에 대해서 모두 pop한다.

6. 5의 과정이 끝나고 새로운 인덱스를 스택에 push한다.

 

7. 마지막에 스택이 비어있지 않다면 오큰수가 없는 인덱스들만 스택에 남은 것이다.

스택이 빌 때까지 모두 pop해주고 정답 수열에서 해당 인덱스를 모두 -1로 변경한다.

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

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, k;

	cin >> N;

	vector<int> A(N, 0);
	vector<int> answer(N + 1, 0);
	stack<int> myStack;

	for (int i = 0; i < N; i++)
		cin >> A[i];

	for (int i = 0; i < N; i++) {

		while (!myStack.empty() && A[i] > A[myStack.top()]) { // if the stack is not empty and its top element value is lower than A[i]
			answer[myStack.top()] = A[i]; // add A[i] to the answer array
			myStack.pop(); // pop the all elements which has NGE
		}

		myStack.push(i); // push the new index

	}

	while (!myStack.empty()) {
		answer[myStack.top()] = -1; // set all the elements which don't have any NGE as -1
		myStack.pop(); // pop all the elements
	}

	for (int i = 0; i < N; i++) {
		cout << answer[i] << " ";
	}

	return 0;

}