6032 : 탑 — 레이저 신호 수신
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
일직선 위에 $N$개의 높이가 서로 다른 탑이 서 있고, 모든 탑은 왼쪽 방향으로 레이저 신호를 보냅니다.
하나의 탑에서 발사된 신호는 왼쪽의 탑 중 자신보다 높이가 높은 최초의 탑에 도달합니다.
각 탑이 보낸 레이저 신호를 어느 탑이 수신하는지 구하는 프로그램을 작성하십시오.
하나의 탑에서 발사된 신호는 왼쪽의 탑 중 자신보다 높이가 높은 최초의 탑에 도달합니다.
각 탑이 보낸 레이저 신호를 어느 탑이 수신하는지 구하는 프로그램을 작성하십시오.
입력 설명
첫째 줄에 탑의 개수 $N$이 주어집니다. ($1 \le N \le 500,000$)
둘째 줄에 $N$개 탑의 높이가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개 탑의 높이가 공백으로 구분되어 주어집니다.
출력 설명
각 탑이 발사한 신호를 수신하는 탑의 번호(1-based)를 공백으로 구분하여 출력합니다. 수신하는 탑이 없으면 0을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
6 9 5 7 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0 0 2 2 4도움
탑을 왼쪽부터 하나씩 탐색합니다. 단조 감소 스택을 유지하며 스택 top의 탑 높이가 현재 탑보다 클 때까지 pop을 수행하고, 찾은 탑 번호를 기록합니다.