백준 17298 - 오큰수 (C/C++)

문제

문제로 이동하기

문제

크기가 $N$인 수열 $A$ = $A_1$, $A_2$ ..., $A_N$이 있다. 수열의 각 원소 $A_i$에 대해서 오큰수 NGE(i)를 구하려고 한다. $A_i$의 오큰수는 오른쪽에 있으면서 $A_i$보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -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$의 원소 $A_1$, $A_2$, ..., $A_N$ (1 ≤ $A_i$ ≤ 1,000,000)이 주어진다.

출력

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

해법 추론

NGE($i$)는 $A_i$의 오른쪽 수중 $A_i$보다 크고 $i$와 가장 가까운 수이다.
따라서 1번부터 순차적으로 값을 비교하는 것이 아닌 $N$번째 수부터 역순으로 가야한다.
일단 NGE($N$) = -1이 자명하니 stack에 N번째 수를 넣고 시작한다.

해법

$A_i$가 스택의 top의 값보다 작으면 NGE($i$)의 값은 stack의 top값이 될 것이다.
반대로 크거나 같다면 스택의 top값은 더이상 NGE($i$)의 값이 될 수 없다 왜냐하면 그보다 큰 수가 왼쪽(현재는 역순이니 오른쪽)에 있기 때문이다. 따라서 이런경우에는 $A_i$가 스택의 top의 값보다 작아질 때까지 pop을 진행해준다.
만약 stack이 전부 빈다면 $A_i$보다 큰 수가 오른쪽에 없기 때문에 NGE($i$) = -1이 될 것이다. stack에 원소가 있다면 NGE($i$)의 값은 stack의 top값이 될 것이다.

이를 통해 시뮬레이션을 돌리면

시뮬레이션

$A = [3, 5, 2, 7]$이라 하면 일단 $A$를 역순으로 돌린다.
$A_r = [7, 2, 5, 3]$이고 NGE(1) = -1, stack[top] = 7인 상태로 시작한다.
stack[top] = 7 > $A_2$ = 2이니 NGE(2) = 7을 삽입하고 stack에 2를 삽입한다. (현재 stack = [7, 2])
stack[top] = 2 < $A_3$ = 5이니 2를 스택에서 pop해주고 NGE(3) = 7을 삽입하고 stack에 5를 삽입한다. (현재 stack = [7, 5])
stack[top] = 5 > $A_4$ = 3이니 NGE(4) = 5를 삽입하고 stack에 3을 삽입한다. (현재 stack = [7, 5, 3])
결과는 NGE = [-1, 7, 7, 5]이다. A를 역순으로 하고 만든 것이기 때문에 출력은 역순으로 다시 바꿔서 해준다.
따라서 정답은 NGE = [5, 7, 7, -1]이 된다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int A[1000005];
int NGE[1000005];
int stack[1000005];

int main(void)
{
	int N, i, j, top = 0, idx = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%d", &A[i]);
	}
	stack[0] = A[N - 1];
	NGE[0] = -1;
	top++;
	idx++;
	for (i = N - 2; i >= 0; i--)
	{
		if (stack[top - 1] > A[i])
		{
			NGE[idx++] = stack[top - 1];
			stack[top++] = A[i];
		}
		else
		{
			while (stack[top - 1] <= A[i] && top > 0)
			{
				top--;
				stack[top] = 0;
			}
			if (top == 0)
			{
				NGE[idx++] = -1;
				stack[top++] = A[i];
			}
			else
			{
				NGE[idx++] = stack[top - 1];
				stack[top++] = A[i];
			}
		}
	}
	for (i = idx - 1; i >= 0; i--)
	{
		printf("%d ", NGE[i]);
	}
	printf("\n");
	

	return 0;
}