문제 설명
숫자로 이루어진 리스트 nums가 주어졌을 때, 기울기가 양수에서 음수로 바뀌거나 음수에서 양수로 바뀌는 지점, 즉 방향이 전환되는 횟수를 구하는 문제입니다.
예를 들어 입력이 [2, 4, 10, 18, 6, 11, 13]이라면 출력은 2가 됩니다. 값이 10에서 증가하다가 감소로 방향을 바꾸고(양수 → 음수), 다시 6에서 감소하다가 증가로 방향을 바꾸기(음수 → 양수) 때문입니다.
해결 방법
이 문제는 각 요소가 이웃한 두 요소와 비교했을 때 극대값(봉우리) 또는 극소값(골짜기)인지 확인하면 해결할 수 있습니다. 구체적인 절차는 다음과 같습니다.
- 인덱스 i를 1부터 len(nums) - 2까지 순회합니다.
- nums[i-1] < nums[i] > nums[i+1] 또는 nums[i-1] > nums[i] < nums[i+1] 조건을 만족하면, 해당 위치에서 방향이 전환된 것이므로 count를 1 증가시킵니다.
- 순회가 끝나면 count를 반환합니다.
구현 예제
class Solution:
def solve(self, nums):
count = 0
for i in range(1, len(nums) - 1):
if nums[i - 1] < nums[i] > nums[i + 1] or nums[i - 1] > nums[i] < nums[i + 1]:
count += 1
return count
ob = Solution()
print(ob.solve([2, 4, 10, 18, 6, 11, 13]))
입력
[2, 4, 10, 18, 6, 11, 13]
출력
2
복잡도 분석
리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 공간은 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 이 알고리즘은 매우 효율적입니다.