6027 : 오큰수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
크기가 $N$인 수열 $A = [A_1, A_2, \dots, A_N]$이 있습니다. 수열의 각 원소 $A_i$에 대해 오큰수를 구하려고 합니다.
$A_i$의 오큰수는 오른쪽 방향에서 $A_i$보다 최초로 큰 수 $A_j$ ($j > i$)를 의미하며, 그러한 수가 존재하지 않으면 -1이 됩니다.
$A_i$의 오큰수는 오른쪽 방향에서 $A_i$보다 최초로 큰 수 $A_j$ ($j > i$)를 의미하며, 그러한 수가 존재하지 않으면 -1이 됩니다.
입력 설명
첫째 줄에 수열의 크기 $N$이 주어집니다. ($1 \le N \le 1,000,000$)
둘째 줄에 수열의 원소 $N$개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 수열의 원소 $N$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
각 원소의 오큰수를 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
3 5 2 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5 7 7 -1도움
단조 감소 스택을 관리합니다. 현재 숫자가 스택 top 인덱스의 숫자보다 크면 스택에서 꺼내며 그 숫자의 오큰수를 현재 숫자로 할당합니다.