[C++] 백준 17299 오등큰

 

#include <iostream>
#include <stack>
 
int arr[1000001] = {};
int ans[1000001] = {};
int nums[1000001] = {};
 
int main() 
{
	int N = 0;
	std::cin >> N;
 
	for (int i = 0; i < N; ++i) 
	{
		std::cin >> nums[i];
		++arr[nums[i]];
	}
 
	std::stack<int> stk = {};
 
	for (int i = N - 1; i >= 0; --i) 
	{
		int height = arr[nums[i]];
 
		while (!stk.empty()) 
		{
			int topHeight = arr[nums[stk.top()]];
 
			if (height >= topHeight)
			{
				stk.pop();
			}
 
			else 
				break;
		}
 
		if (stk.empty())
		{
			ans[i] = -1;
		}
 
		else
		{
			ans[i] = nums[stk.top()];
		}
 
		stk.push(i);
	}
 
	for (int i = 0; i < N; ++i)
	{
		std::cout << ans[i] << " ";
	}
 
	return 0;
}

이전에 푼 문제(17298)랑 거의 똑같습니다.

 

스택을 이용해서 풀었어야 합니다.

처음에 입력을 하고 뒤에서부터 찾아합니다.

앞쪽에서 검색을 하려면 가장 마지막 수를 찾기 위해서

다시 맨뒤로 돌아가야하기 때문에 뒤에서부터 stack에 추가합니다.

입력을 하기 전에 현재 수보다 스택 안에 있는 수의 갯수가 큰지 확인을 해야합니다.

스택 안에 맨 위의 수(오른쪽으로 가장 큰 수)의 갯수가 현재의 수의 갯수보다 크다면

해당 순서에 맨 위의 수를 넣어놓고 현재 수를 stack에 추가합니다.

현재의 수의 개수보다 크지 않다면 현재의 수의 개수가 오른쪽에 있는 수의 개수보다 더 크기 때문에

stack에서 현재의 수의 개수보다 더 큰 개수가 나오기 전까지 빼줍니다.

stack에 현재 값보다 큰 수가 없는 경우는 해당 순서에는 -1을 넣어놓습니다.

그리고 다음 순서를 찾기 위해 stack에 현재 값을 넣어줍니다.