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

오른쪽으로 가면서 제일 가까우면서 자신보다 큰 친구를 찾는 문제이다.

 

수열의 크기가 100만까지 주어지기 때문에 이중 for문을 이용해서 문제를 해결하려고 하면 시간초과가 발생한다.

효율적으로 자신보다 큰 사람을 찾아야 한다.(어떻게 해결??)

 

숫자를 뒤에서부터 하나씩 stack에 넣으면서 top과 비교하는 방식을 사용하였다.

7을 stack에 넣는다.

2를 stack에 넣는다.

5를 넣는다.

stack에는 5 2 7이 들어가 있는데 여기서 우리가 주의 깊게 봐야 할 숫자는 2이다.

만약 다음으로 오는 숫자가 (1||2||3||4)이면 5가 출력이 될 것이고

다음으로 오는 숫자가 6이면 7이 출력이 된다.

2라는 숫자는 사실상 이제 필요가 없다. 왜냐하면 5가 2보다 크기 때문에 걸려도 5에서 걸리지 2에서는 걸리지 않는다.

스택에 넣을 숫자가 현재 stack의 top보다 크면 stack을 pop 한다.

7은 5보다 크기 때문에 pop 하지 않는다.(왜??? 다음으로 6이 들어오면 7에서 걸려야 하기 때문이다. 만약 6이 들어오면 5는 필요 없는 숫자가 되어서 pop이 될 것이다.)

 

stack에 숫자를 넣을 때 top의 값과 비교를 해서 없애주는 작업을 진행해 주면 된다. 이러한 작업을 함으로써 시간복잡도를 줄일 수 있다. 시간복잡도는 처음 for문이 O(n)이고 pop을 하는 과정은 많아도 O(n) 그렇기에 총 시간 복잡도는 O(n)이다.

 

#include <iostream>
#include <stack>
using namespace std;
int arr[1000001];
int NGE[1000001];
int main(void)
{
	stack<int> s;
	int a = 0;
	cin >> a;
	for (int i = 0; i < a; i++)
	{
		cin >> arr[i];
	}

	for (int i = a - 1; i >= 0; i--)
	{
		while (!s.empty() && s.top() <= arr[i])//만약 arr[i]가 6이고 스택의 모습이 5, 8이면?? 5를 팝해야겠지? 
		{
			s.pop();
		}
		if (s.empty())
		{
			NGE[i] = -1;
		}
		else
		{
			NGE[i] = s.top();
		}
		s.push(arr[i]);
	}
	for (int i = 0; i < a; i++)
	{
		cout << NGE[i] << " ";
	}
	return 0;
}

 

만약 배열의 뒤에서부터 탐색을 하는 것이 아닌 앞에서부터 탐색을 하면 어떻게 될까??

 

넣으려는 값과 stack의 top을 비교해서 top이 더 작다면 넣으려는 값이 stack top의 오큰수 이다.

넣으려는 값이 top보다 더 크다면 stack을 pop한다.

위 과정을 while문을 통해 stack top의 값이 넣으려는 값보다 커질 때까지 반복한다.(stack이 비어있으면 바로 push)

 

3의 오큰수는 5이다.

top의 값이 넣으려고 하는 값(2)보다 크기 때문에 아직 top의 오큰수는 결정되지 않음.

넣으려고 하는 값이 2보다 크기 때문에 2의 오큰수는 7

5 또한 7보다 작기 때문에 5의 오큰수는 7이다.

 

push 하려는 값보다 top의 값이 작으면 top의 오큰수는 push 하려는 값이 된다.

top의 오큰수는 결정이 되었기 때문에 stack에 남아있을 필요가 없다. pop 해준다.

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> arr;
int result[1000000];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N = 0;
	cin >> N;
	int idx = 0;
	for (int i = 0; i < N; i++)
	{
		int num = 0;
		cin >> num;
		for (int j = arr.size() - 1; j >= 0; j--)
		{
			if (arr[j].first < num)
			{
				result[arr[j].second] = num;
				arr.pop_back();
			}
			else
			{
				break;
			}
		}
		arr.push_back({ num,i });
	}

	for (int i = 0; i < N; i++)
	{
		if (result[i] == 0)
		{
			cout << -1 << " ";
		}
		else
		{
			cout << result[i] << " ";
		}
	}
	return 0;
}// 3 5 2 3 7