Find Peak Element
배열 nums는 올라갔다가 내려갑니다. 즉, 어떤 인덱스에 도달할 때까지 각 값은 바로 앞의 값보다 크고, 그 인덱스 이후의 각 값은 바로 앞의 값보다 작습니다. 어느 한쪽 부분은 비어 있을 수 있으므로, 배열은 올라가기만 하거나 내려가기만 할 수도 있습니다. 전환 인덱스의 값이 꼭대기이며, 이 값은 양옆의 모든 값보다 큰 유일한 값입니다.
O(log n) 시간에 꼭대기의 인덱스를 반환하세요.
함수
- numsinteger-array
- 값은 상승하여 하나의 정점에 도달한 다음 하락한다
- 반환값integer
- 최고점의 인덱스
제약 조건
1 ≤ nums.length ≤ 5000-106 ≤ nums[i] ≤ 106nums[i] != nums[i+1]가 모든 유효한i에 대해 성립합니다.nums는 한 인덱스까지 엄격히 증가하고 그 이후에는 엄격히 감소하므로, 꼭짓점은 정확히 하나입니다.
예제
- 입력
- nums = [2, 5, 9, 4, 1]
- 출력
- 2
- 설명
- 값은 2, 5, 9로 올라간 다음 4와 1로 내려갑니다. 전환점은 9이며, 인덱스는 2입니다.
- 입력
- nums = [8, 6, 3, -2]
- 출력
- 0
- 설명
- 배열은 내림차순으로만 이어지므로 오르는 부분은 비어 있고, 꼭대기는 첫 번째 값인 8이며 인덱스는 0입니다.
- 입력
- nums = [-7, -3, 0, 12, 40]
- 출력
- 4
- 설명
- 배열은 계속 증가하므로 최댓값은 마지막 값인 인덱스 4의 40입니다. 음수 값은 아무것도 바꾸지 않습니다.
후속 질문
서로 인접한 두 셀의 값이 같은 셀이 없는 격자에서, 봉우리는 최대 네 개의 이웃 셀보다 값이 큰 셀입니다. 모든 셀을 읽지 않고도 봉우리를 찾을 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
인덱스
mid를 아무거나 선택하고nums[mid+1]을 살펴보세요. 그 단계의 방향은 봉우리가 어디에 있는지에 대해 무엇을 알려 주나요?단계가 증가하는 것은 정점 이전에만 발생하고, 단계가 감소하는 것은 정점에서 또는 정점 이후에만 발생합니다. 따라서 비교 한 번으로
mid의 한쪽을 배제할 수 있습니다.최댓값을 항상 포함하는 범위를 유지하세요. 한 단계 위로 올라가면
lo를mid+1로 옮기고, 그렇지 않으면hi를mid로 옮기세요. 두 값이 만날 때 멈추세요.
풀이
단일 봉우리가 있을 때 봉우리는 가장 큰 값이므로, 한 번 순회하면 O(n)에 찾을 수 있습니다. O(log n)에 찾으려면 nums[mid]와 nums[mid+1]을 비교하세요. mid에서의 기울기를 보면 봉우리의 어느 쪽에 있는지 알 수 있으므로, 매 단계마다 범위를 절반으로 줄일 수 있습니다.
값이 떨어지기 시작할 때까지 걷기
핵심 아이디어
정점 이전에는 모든 값이 다음 값보다 작고, 정점부터는 모든 값이 다음 값보다 큽니다. 따라서 정점은 nums[i] > nums[i+1]인 첫 번째 인덱스 i이며, 배열이 계속 오르기만 한다면 마지막 인덱스입니다.
5000개의 값 중 정점이 끝에 있으면, 순차 탐색은 4999번 비교하지만 이진 탐색은 13번 비교하면 됩니다.
알고리즘
i를 0부터n-2까지 순회하며nums[i]와nums[i+1]을 비교합니다.nums[i]가 더 큰 첫 번째i에서i를 반환합니다.- 반복문이 감소하는 값 없이 끝나면
n-1을 반환합니다.
def findPeakElement(nums):
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return i # the first step down starts at the peak
return len(nums) - 1 # never went down: the last value is the peak기울기에 대한 이진 탐색
핵심 아이디어
nums[mid]와 nums[mid+1] 한 쌍을 확인합니다. 한 단계 올라간다는 것은 배열이 여전히 상승 중이라는 뜻이며, 이 배열에서는 꼭짓점 이전에서만 일어납니다. 즉, 꼭짓점은 mid+1 또는 그 오른쪽에 있습니다. 한 단계 내려간다는 것은 꼭짓점에 있거나 꼭짓점을 지난 상태라는 뜻입니다. 즉, 꼭짓점은 mid 또는 그 왼쪽에 있습니다.
항상 꼭짓점을 포함하는 범위 [lo, hi]를 유지합니다. 한 단계 올라가면 lo를 mid+1로 옮깁니다. 한 단계 내려가면 꼭짓점일 수도 있는 mid를 유지하면서 hi를 mid로 옮깁니다. lo와 hi가 만나면 남은 인덱스가 꼭짓점입니다. mid를 내림하면 hi보다 작게 유지되므로 mid+1은 항상 존재합니다.
첫 번째 예시에서는 mid = 2일 때 9 > 4이므로 hi = 2입니다. 그런 다음 mid = 1일 때 5 < 9이므로 lo = 2가 되고, 이 위치가 꼭짓점입니다. 값이 5000개라면 최대 13단계가 걸립니다.
알고리즘
lo = 0과hi = n-1을 설정합니다.lo < hi인 동안mid = lo + (hi - lo) / 2를 구하고, 소수점 이하를 버립니다.nums[mid] < nums[mid+1]이면lo = mid + 1을 설정합니다.- 그렇지 않으면
hi = mid를 설정합니다. lo를 반환합니다.
def findPeakElement(nums):
lo, hi = 0, len(nums) - 1 # the peak is always inside [lo, hi]
while lo < hi:
mid = lo + (hi - lo) // 2 # mid < hi, so mid + 1 is a valid index
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # still climbing: the peak is to the right of mid
else:
hi = mid # going down: the peak is mid or to its left
return lo
함정과 경계 사례
- 내려가는 단계에서
hi = mid - 1을 설정하는 것.[2, 5, 9, 4, 1]에서는 첫 번째mid가 피크 자체인데,hi = 1로 설정하면 피크를 제외하게 되어 검색 결과로 1을 반환한다. mid를 내림할 때nums[mid-1]와 비교하는 것.mid가 0일 수 있으며, 이때는 왼쪽 이웃이 없다.hi = n인 반개구간을 사용하는 것. 그러면mid가n-1일 수 있고,nums[mid+1]은 끝을 넘어 읽게 된다. 값이 하나뿐인 경우에도 바로 문제가 발생한다.- Lua와 R에서 인덱스 이동을 잊는 것. 답은 여전히 0부터 시작하는 인덱스이므로, 위치
i는i-1로 반환된다.
자주 묻는 질문3
Find Peak Element의 시간 복잡도는 얼마인가요?
이진 탐색은 O(log n) 시간과 O(1) 공간으로 실행되며, 값이 5000개일 때 최대 13단계가 걸립니다. 왼쪽부터 순회하는 방법은 감소 지점을 찾기 전에 모든 쌍을 읽을 수도 있으므로 O(n)입니다.
피크가 여러 개일 때도 이진 검색이 여전히 작동하나요?
네, 이웃한 값들이 서로 다르고 양 끝 너머의 지점이 모든 값보다 낮은 것으로 간주된다면 가능합니다. 이 함수는 항상 가장 높은 봉우리가 아니라 봉우리 하나를 반환합니다. 한 단계 올라간 뒤에는 늦어도 범위 끝까지 값이 내려가야 하며, 첫 번째 방향 전환 지점이 봉우리이므로 탐색에서 계속 선택하는 쪽에는 항상 봉우리가 하나 있습니다.
최고점은 항상 가장 큰 값인가요?
이 문제에서는 배열이 하나의 꼭짓점까지 올라간 뒤 내려오므로, 다른 어떤 값도 더 클 수 없습니다. 여러 개의 꼭짓점이 있는 버전에서는 그렇지 않습니다. 양쪽 이웃보다 큰 값은 무엇이든 꼭짓점으로 간주되기 때문입니다. 그래서 최댓값을 찾는 대신 이웃한 값들을 비교합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def findPeakElement(nums):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
nums = [2, 5, 9, 4, 1]
예상 출력
2