[C++] 백준 17299번: 오등큰수

🔗 문제

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

 

✏️ 풀이

 

입력되는 N의 개수는 1,000,000 (백만)이다.

숫자의 크기 또한 최대 1,000,000 (백만)이다.

 

가장 나이브하게 할 수 있는 방법 Ai 마다 F 배열을 탐색하면 O(백만 X 백만) => 시간초과다. 

 

어떻게 푸는지 모르겠어서 30분 고민했는데 모르겠어서 답을 봤다. 

일단 유형이 stack이었고, 나는 그걸 생각해 내지 못했으니까 문제에서 무엇을 보고 알고리즘을 유추했어야 했는지 해석하는 풀이를 올리겠다. 

 

 

stack에는 idx가 들어간다. 값이 아니라 idx가 들어가는 이유는 답을 idx 순으로 출력해주어야 하기 때문이다. 

 

stack에 저장되는 조건은 F[idx]가 stk.top()에 들어 있는 숫자보다 작거나 같을 때만 들어갈 수 있다.

즉, arr[idx]의 오등큰수가 "아닌 경우"에만 들어가게 된다. 

 

이 경우가 아니라면 오등큰수다. 그 현재 값을 now가 stk.top()의 오등큰수라는 의미인데 stk의 이전값도 값을 넣어주어야 하니 while문을 사용해 준다. 

 

주석을 참고해서 코드를 보면 이해하기 쉬울 것 같은데 이해가 안 가는 사람은 댓글 달아주세요..

그림을 그리면 이해가 쉬울 것 같은데 그림을 올리기 힘듦!!

 

 

[도움 됐던 반례]

제출하자마자 틀렸다면 이걸 보세요 

출처 : https://www.acmicpc.net/board/view/141791

8
2 1 1 1 2 3 3 3
    
ans :
1 -1 -1 -1 3 -1 -1 -1

 

 

💾  소스

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int MAX = 1000000 + 1;

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

	vector<int> arr(N + 1);
	vector<int> ngf(N + 1, -1);
	vector<int> F(MAX, 0);
	stack<int> stk;

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

	for (int i=0; i<N; ++i)
	{
		int now = arr[i];

		while (!stk.empty())
		{
			int idx = stk.top();
			int top = arr[idx];

			// 아래 조건 덕분에 F가 작은 숫자 순으로 계속 쌓이게 됨
			if(F[top] >=  F[now]) break;

			// 그러다가 현재의 F가 이전의 F보다 크다는건 ? 이전의 F 오등큰수를 찾았다는 것!
			// 이전 값의 인덱스의 오등큰수는 현재 값이다. 
			ngf[idx] = now;
			stk.pop();
		}
		stk.push(i);
	}

	for (int i=0; i<N; ++i)
		cout << ngf[i] << ' ';

	return 0;
}