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

문제

크기가 N인 수열 A = A1, A2, …, AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A₁, A₂, …, A_N (1 ≤ A_i ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), …, NGE(N)을 공백으로 구분해 출력한다.

예제 입력 1

4
3 5 2 7

예제 출력 1

5 7 7 -1

풀이

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

using namespace std;
using std::endl;
using std::cin;
using std::cout;

int main() {
	
	int test;
	int temp = 0;
	cin >> test;
	stack <int> st;
	vector <int> arr(test), ans(test,-1);

	for (int i = 0; i < test; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < test; i++) {
		while (!st.empty() && arr[st.top()] < arr[i]) {
			ans[st.top()] = arr[i];
			st.pop();
		}
		st.push(i);
	}

	for (int i = 0; i < test; i++) cout << ans[i] << " ";

	
	return 0;
}

알고리즘 [ 접근방법 ]

처음에는 단순히 배열을 이용해 값끼리 비교해서 출력을 해보려 했지만 이 방법은 시간 초과라는 결과를 초래할 것 같아 버렸다.

그다음은 Queue를 이용해 선입후출 구조를 활용해보려 했지만 답이 나오지 않았다.

결국 한시간정도 고민 끝에 방법을 찾지 못해 구글링을 하게 되었다.

답은 Stack과 Vector를 활용하는 것이였다.

하나의 벡터에는 입력받은 값을 넣어주고 다른 하나의 벡터에는 결과를 입력한다.

스택에는 입력받은 벡터의 Index를 넣어준다. Index를 활용한 문제를 몇번 풀어봤지만 여기서 활용할거라고는 생각을 못했다.

스택의 top과 배열의 값을 비교해주면서 ans에 오큰수를 넣어준다.