🎁 오큰수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	27485	9292	6775	33.598%

문제
크기가 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의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

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

예제 입력 1

4
3 5 2 7

예제 출력 1

5 7 7 -1

예제 입력 2

4
9 5 4 8

예제 출력 2

-1 8 8 -1

---

🙄 구현

• 오큰수 NGE(index) : index 에 해당하는 수보다 오른쪽에 있으면서 큰 수 중에 가장 왼쪽에 있는 수.

• 입력을 n 개만큼 받자 ( i = 0 ; i < n ; i ++)
  만약 stack 이 비워져있다면 입력받은 순간 바로 스택에 pair<index,value>로 push!

• 만약 stack 이 비워져있지 않다면 오큰수찾으러 ㄱㄱ

• stack.top().second 와 입력값을 비교하여, 입력값이 크다면 그것이 바로 오큰수
  해당 조건은 while 문에 넣어서, 만족하면 오큰수를 저장 및 stack.pop() 해준다.
  while 문 내에서 만약 stack의 사이즈가 0이라면, 더 찾을 오큰수가 없는것이므로 탈출

• while 문을 탈출하면, 입력받은 i와 present_value 를 stack 에 push!

  위 과정을 입력 개수만큼 반복해주자!
  잘 생각해보면, 입력 받을때마다 오큰수가 있는지 판단해주는데 만약에 오큰수가 바로 옆에 있으면 곧바로 오큰수를 저장하고 스택을 pop 해준다. 만약에 오큰수가 바로 옆에 없으면 다음 입력에서 찾아야 하니까 pop()을 하지 않고, 일단 현재 입력받은 수와 인덱스를 stack 에 push 해서 쌓아준다. 그러면 또 새로운 인풋을 받을 거고, 이 인풋이랑 현재 top() 을 비교해서 오큰수를 찾아준다. 만약에 오큰수를 찾게 되면 pop 을 할텐데, 여전히 스택에 ' 이전에 찾지 못한 오큰수를 찾아야 하는 원소 ' 가 남아있으므로 while 문을 탈출하지 못하고 현재 인풋이 그 원소의 오큰수인지 검사하게 된다. 만약 오큰수가 맞다면 stack.top().first 인덱스에 해당하는 result배열에 오큰수[ = 현재 입력 ] 을 저장해주고 만약, 오큰수가 아니다? 그러면 그냥 while문을 탈출하게 된다.
  이러한 과정을 입력받은 원소 개수만큼 반복하게 되는데, 끝까지 오큰수를 못찾은 경우 -1 을 출력해야한다. 우리는 result 배열을 따로 선언해서 오큰수를 한번에 출력하려고 하는데, 애초에 result 를 memset 함수를 이용해서 -1 로 초기화를 해주면 된다. (업데이트가 안되면 사실 오큰수가 없는거니까!)

  😅 내 코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	int result[1000001] = { 0, };
	memset(result,-1, sizeof(result));
	stack<pair<int, int>> _stack;

	int present_input;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> present_input;
		
		if (_stack.empty() == true)
		{
			_stack.push({ i,present_input });
			continue;
		}
		else
		{
			while (_stack.top().second < present_input)
			{
				result[_stack.top().first] = present_input;
				_stack.pop();
				if (_stack.size() == 0) break;
			}
			_stack.push({ i,present_input });

		}
	}

	for (int i = 0; i < n; i++)
	{
		cout << result[i] << ' ';
	}

	return 0;
}