7027 : 봉우리 원소 찾기
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 2
•통과: 1
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 리스트가 주어집니다. 이 중에서 봉우리 원소(Peak Element)를 모두 찾고자 합니다.
봉우리 원소란 자신의 양옆에 있는 이웃 원소들보다 크기가 큰 원소를 말합니다. 리스트의 양 끝 원소(첫 번째와 마지막 원소)는 이웃이 하나뿐이므로, 그 하나의 이웃보다 크면 봉우리 원소로 인정됩니다.
예를 들어,
- $3$은 $1$과 $2$보다 크므로 봉우리입니다. (인덱스 $1$)
- $5$는 $4$보다 크므로 봉우리입니다. (인덱스 $4$)
봉우리 원소들의 인덱스들을 모두 찾아 오름차순으로 출력하는 프로그램을 작성하십시오.
[제약 조건]
• 리스트 크기 $N$: $1 \le N \le 100{,}000$
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
봉우리 원소란 자신의 양옆에 있는 이웃 원소들보다 크기가 큰 원소를 말합니다. 리스트의 양 끝 원소(첫 번째와 마지막 원소)는 이웃이 하나뿐이므로, 그 하나의 이웃보다 크면 봉우리 원소로 인정됩니다.
예를 들어,
[1, 3, 2, 4, 5]의 경우:- $3$은 $1$과 $2$보다 크므로 봉우리입니다. (인덱스 $1$)
- $5$는 $4$보다 크므로 봉우리입니다. (인덱스 $4$)
봉우리 원소들의 인덱스들을 모두 찾아 오름차순으로 출력하는 프로그램을 작성하십시오.
[제약 조건]
• 리스트 크기 $N$: $1 \le N \le 100{,}000$
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
입력 설명
첫째 줄에 리스트의 크기 $N$ ($1 \le N \le 100000$)이 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. 각 정수의 범위는 $-10^9$ 이상 $10^9$ 이하입니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. 각 정수의 범위는 $-10^9$ 이상 $10^9$ 이하입니다.
출력 설명
봉우리 원소들의 인덱스($0$-based)를 공백으로 구분하여 오름차순으로 한 줄에 출력합니다.
만약 봉우리 원소가 존재하지 않는다면 `-1`을 출력합니다.
만약 봉우리 원소가 존재하지 않는다면 `-1`을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 3 2 4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 4도움
인덱스 $0$인 원소는
arr[0] > arr[1]인지 확인하고, 인덱스 $N-1$인 원소는 arr[n-1] > arr[n-2]인지만 검사합니다. 그 외의 $1$부터 $N-2$까지의 원소 $i$에 대해서는 arr[i] > arr[i-1]이고 arr[i] > arr[i+1]인지를 검사하여 만족하는 인덱스를 수집합니다.