6028 : 오왼수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
수열 $A$의 각 원소 $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
복사되었습니다!
복사되었습니다!
-1 -1 5 -1도움
오큰수 알고리즘과 대칭 구조입니다. 수열을 오른쪽 끝(인덱스 $N-1$)에서부터 왼쪽 방향으로 탐색하며 단조 스택을 활용합니다.