크기가 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 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int N, *A=NULL, *NGE=NULL, *stack=NULL, current=0;
scanf("%d", &N);
A=(int *)malloc(N*sizeof(int));
NGE=(int *)calloc(N,sizeof(int));
stack=(int *)malloc(N*sizeof(int));
for(int n=0;n<N;n++)
{
scanf("%d", &A[n]);
while(current>0)
if(A[stack[current-1]]<A[n])
NGE[stack[--current]]=A[n];
else
break;
stack[current++]=n;
}
for(int n=0;n<N;n++)
printf("%d ", NGE[n]==0?-1:NGE[n]);
printf("\n");
free(NGE);
free(stack);
free(A);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 12865번: 평범한 배낭 (0) | 2023.02.09 |
---|---|
<백준 알고리즘> 16953번: A → B (0) | 2023.02.08 |
<백준 알고리즘> 15665번: N과 M (11) (0) | 2023.02.08 |
<백준 알고리즘> 15663번: N과 M (9) (0) | 2023.02.08 |
<백준 알고리즘> 15664번: N과 M (10) (0) | 2023.02.08 |