문제 개요
숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 우리의 목표는 이 리스트 안에 있는 모든 피크(peak, 봉우리) 요소의 인덱스를 찾아내는 것입니다.
여기서 인덱스 i가 피크가 되는 조건은 다음과 같습니다.
- i = 0일 때: nums[i] > nums[i + 1]
- i = n - 1일 때: nums[i] > nums[i - 1]
- 그 외의 경우: nums[i - 1] < nums[i] > nums[i + 1]
즉, 리스트의 첫 번째 요소는 오른쪽 이웃보다, 마지막 요소는 왼쪽 이웃보다 클 때 피크이며, 나머지 요소는 양쪽 이웃보다 모두 커야 합니다.
예를 들어 입력이 nums = [5, 6, 7, 6, 9]라면 출력은 [2, 4]가 됩니다. 인덱스 2의 값 7은 양쪽 이웃(6, 6)보다 크고, 인덱스 4의 값 9는 왼쪽 이웃(6)보다 크기 때문입니다.
풀이 접근 방법
이 문제는 리스트를 한 번만 순회하면서 각 요소가 피크 조건을 만족하는지 확인하면 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- 결과를 저장할 빈 리스트
ans를 생성합니다. - 리스트의 길이를
n에 저장합니다. - n이 1이라면 비교할 이웃이 없으므로 빈 리스트를 그대로 반환합니다.
enumerate()를 사용해 각 인덱스 i와 값 num을 순회하며 아래 조건을 검사합니다.- 첫 번째 요소(i == 0): num이 오른쪽 이웃보다 크면 피크입니다.
- 중간 요소(0 < i < n - 1): num이 양쪽 이웃보다 모두 크면 피크입니다.
- 마지막 요소(i == n - 1): num이 왼쪽 이웃보다 크면 피크입니다.
- 피크 조건을 만족하는 인덱스를 ans에 추가한 뒤, 순회가 끝나면 ans를 반환합니다.
예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(nums):
ans = []
n = len(nums)
if n == 1:
return ans
for i, num in enumerate(nums):
if i > 0 and i < n - 1:
if nums[i - 1] < num > nums[i + 1]:
ans.append(i)
if i == 0:
if num > nums[i + 1]:
ans.append(i)
if i == n - 1:
if num > nums[i - 1]:
ans.append(i)
return ans
nums = [5, 6, 7, 6, 9]
print(solve(nums))입력
[5, 6, 7, 6, 9]
출력
[2, 4]
복잡도 분석
- 시간 복잡도: O(n) — 리스트를 한 번만 순회하므로 입력 크기에 비례합니다.
- 공간 복잡도: O(n) — 최악의 경우 모든 인덱스가 피크일 수 있어 결과 리스트가 n개까지 늘어날 수 있습니다.