Python에서 리스트의 로컬 피크(봉우리) 인덱스를 찾는 방법

숫자로 이루어진 리스트 nums가 주어졌을 때, 모든 피크(peak) 요소의 인덱스를 오름차순으로 정렬하여 찾아야 합니다. 특정 인덱스 i가 피크가 되려면 다음 세 가지 조건을 모두 만족해야 합니다.

1. 오른쪽 방향에서 nums[i]와 다른 값을 가지는 첫 번째 숫자가 존재하지 않거나, 그 값이 nums[i]보다 작아야 합니다.
2. 왼쪽 방향에서 nums[i]와 다른 값을 가지는 첫 번째 숫자가 존재하지 않거나, 그 값이 nums[i]보다 작아야 합니다.
3. 왼쪽 또는 오른쪽 어느 한쪽이라도 nums[i]와 다른 숫자가 최소 하나 이상 존재해야 합니다.

예를 들어 입력이 nums = [5, 8, 8, 8, 6, 11, 11]이라면 출력은 [1, 2, 3, 5, 6]입니다. 연속된 세 개의 8(인덱스 1, 2, 3)과 두 개의 11(인덱스 5, 6)이 각각 하나의 피크 구간, 즉 플래토(plateau)로 간주되기 때문입니다.

풀이 접근 방식

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• n := nums의 길이
• ans := 결과를 저장할 새로운 리스트
• i := 0
• i < n인 동안 다음을 반복합니다.
  • i0 := i (현재 구간의 시작 인덱스)
  • i < n이고 nums[i]가 nums[i0]와 같은 동안 i를 1씩 증가시켜 같은 값 구간 전체를 한 번에 건너뜁니다.
  • (i0이 0이거나 nums[i0] > nums[i0 - 1])이고 (i가 n이거나 nums[i0] > nums[i])라면 현재 구간은 피크입니다.
  • 단, i0이 0이 아니거나 i가 n이 아닌 경우, 즉 양쪽 중 한쪽이라도 다른 값이 존재할 때만 ans에 i0부터 i-1까지의 인덱스를 추가합니다.
• ans를 반환합니다.

핵심 아이디어는 연속된 같은 값들을 하나의 블록으로 묶어 처리한 뒤, 해당 블록의 양쪽 경계값과 비교하여 피크 여부를 판단하는 것입니다. 이렇게 하면 플래토 구간도 자연스럽게 하나의 피크로 인식됩니다.

구현 예제

다음 구현을 통해 더 잘 이해할 수 있습니다.

def solve(nums):
    n = len(nums)
    ans = []
    i = 0
    while i < n:
        i0 = i
        while i < n and nums[i] == nums[i0]:
            i += 1
        if (i0 == 0 or nums[i0] > nums[i0 - 1]) and (i == n or nums[i0] > nums[i]):
            if i0 != 0 or i != n:
                ans.extend(range(i0, i))
    return ans

nums = [5, 8, 8, 8, 6, 11, 11]
print(solve(nums))

입력

[5, 8, 8, 8, 6, 11, 11]

출력

[1, 2, 3, 5, 6]

복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 결과 저장 외에는 추가 공간이 거의 필요하지 않으므로 공간 복잡도 역시 효율적입니다. 리스트의 크기가 커져도 선형 시간 안에 모든 피크 인덱스를 찾을 수 있다는 점이 이 접근 방식의 장점입니다.