백준 17299번 오등큰수

문제 링크입니다: https://www.acmicpc.net/problem/17299

17299번: 오등큰수

N이 최대 1,000,000이기 때문에 O(N^2) 풀이법을 사용하여 풀었다면 TLE가 발생하는 문제였습니다.

따라서 저는 스택을 이용하여 역순으로 확인하며 결과들을 result 배열에 저장했습니다.

자세한 풀이는 주석을 확인해주시면 될 것 같습니다.

 

	#include <iostream>
	#include <stack>
	using namespace std;
	const int MAX = 1e6 + 10;
	int arr[MAX];
	int visited[MAX];
	int result[MAX];
	stack<pair<int, int>> st;
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
	cin >> arr[i];
	visited[arr[i]]++;
	}
	// 맨 뒤에 있는 숫자부터 확인
	for (int i = N - 1; i >= 0; i--)
	{
	// 현재 위치한 숫자가 발생한 빈도보다 스택의 top에 있는 빈도가 작거나 같다면 pop
	while (!st.empty() && visited[arr[i]] >= st.top().first)
	{
	st.pop();
	}
	// 오른쪽에 조건을 만족하는 숫자가 없다면 -1 있다면 스택의 top
	result[i] = st.empty() ? -1 : st.top().second;
	// 스택에는 계속 추가해줘야 함 {해당 숫자 빈도수, 해당 숫자}
	st.push({ visited[arr[i]], arr[i] });
	}
	for (int i = 0; i < N; i++)
	{
	cout << result[i] << " ";
	}
	cout << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~