문제 설명
n개의 타워가 가장 왼쪽을 기준으로 1번부터 n 번 타워까지 일렬로 세워져 있습니다.
k 번 타워에 대하여 k 번 타워보다 오른쪽에 있으면서 높이가 더 큰 타워 중 k 번 타워와 가장 가까운 타워를 k 번 타워의 "오큰타워"라고 합니다.
각 타워의 높이를 담은 일차원 배열 tower가 주어질 때, 타워별로 "오큰타워"의 높이를 차례로 반환하는 solution 함수를 작성하시오.
만약 몇몇 타워에 대해 "오큰타워"가 존재하지 않는다면, 해당 타워에 대한 "오큰타워"의 높이를 -1로 반환합니다.
제한 사항
tower의 길이는 1 이상 1,000,000 이하입니다.tower의 원소는 1 이상 1,000,000 이하의 자연수입니다.
예시 테스트케이스 설명
| 테스트케이스 번호 | tower | return |
|---|---|---|
| 1 | [3,5,2,7] | [5,7,7,-1] |
| 2 | [9,5,4,8] | [-1,8,8,-1] |
| 3 | [2,7,7,9,3,1] | [7,9,9,-1,-1,-1] |
1번 테스트케이스 설명
- 타워별 오큰타워는 아래와 같습니다.
- 1번 타워(높이 3)보다 오른쪽에 있으면서 높이가 더 큰 타워는 2번, 4번 타워입니다. 이 중 1번 타워와 가장 가까운 타워는 2번 타워(높이 5)입니다.
- 2번 타워(높이 5)보다 오른쪽에 있으면서 높이가 더 큰 타워는 4번 타워(높이 7)뿐입니다.
- 3번 타워(높이 2)보다 오른쪽에 있으면서 높이가 더 큰 타워는 4번 타워(높이 7)뿐입니다.
- 4번 타워(높이 7)보다 오른쪽에 있으면서 높이가 더 큰 타워는 없습니다.
- 따라서
[5,7,7,-1]을 반환합니다.
2번 테스트케이스 설명
- 타워별 오큰타워는 아래와 같습니다.
- 1번 타워(높이 9)보다 오른쪽에 있으면서 높이가 더 큰 타워는 없습니다.
- 2번 타워(높이 5)보다 오른쪽에 있으면서 높이가 더 큰 타워는 4번 타워(높이 8)뿐입니다.
- 3번 타워(높이 4)보다 오른쪽에 있으면서 높이가 더 큰 타워는 4번 타워(높이 8)뿐입니다.
- 4번 타워(높이 8)보다 오른쪽에 있으면서 높이가 더 큰 타워는 없습니다.
- 따라서
[-1,8,8,-1]을 반환합니다.
3번 테스트케이스 설명
- 타워별 오큰타워는 아래와 같습니다.
- 1번 타워(높이 2)보다 오른쪽에 있으면서 높이가 더 큰 타워는 2번, 3번, 4번 타워입니다. 이 중 1번 타워와 가장 가까운 타워는 2번 타워(높이 7)입니다.
- 2번 타워(높이 7)보다 오른쪽에 있으면서 높이가 더 큰 타워는 4번 타워(높이 9)뿐입니다.
- 3번 타워(높이 7)보다 오른쪽에 있으면서 높이가 더 큰 타워는 4번 타워(높이 9)뿐입니다.
- 4번 타워(높이 9)보다 오른쪽에 있으면서 높이가 더 큰 타워는 없습니다.
- 5번 타워(높이 3)보다 오른쪽에 있으면서 높이가 더 큰 타워는 없습니다.
- 6번 타워(높이 1)보다 오른쪽에 있으면서 높이가 더 큰 타워는 없습니다.
- 따라서
[7,9,9,-1,-1,-1]을 반환합니다.