숫자 리스트 nums가 주어졌을 때, 이 리스트의 요소들이 등차수열(Arithmetic Progression, AP)을 이루는지 확인해야 합니다. 등차수열이란 인접한 두 요소 사이의 공차(공통 차이)가 항상 일정한 수열을 의미합니다.
예를 들어 입력이 nums = [9, 1, 17, 5, 13]이라면 출력은 True입니다. 요소들을 정렬하면 [1, 5, 9, 13, 17]이 되고, 각 인접한 두 요소의 차이가 모두 4로 동일하기 때문입니다.
풀이 접근 방법
이 문제는 다음 단계로 해결할 수 있습니다.
- 리스트 nums를 오름차순으로 정렬합니다.
- nums의 요소 개수가 1보다 크면 공차 const를 nums[1] - nums[0]으로 설정합니다.
- 요소가 1개 이하라면 자동으로 등차수열이므로 True를 반환합니다.
- 0부터 len(nums)-1까지 반복하면서 각 인접 요소의 차이(nums[i+1] - nums[i])가 공차와 다르면 False를 반환합니다.
- 모든 차이가 일치하면 True를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 더 쉽게 이해할 수 있습니다.
def solve(nums):
nums = sorted(nums)
if len(nums) > 1:
const = nums[1] - nums[0]
else:
return True
for i in range(len(nums)-1):
if nums[i+1] - nums[i] != const:
return False
return True
nums = [9,1,17,5,13]
print(solve(nums))입력
[9,1,17,5,13]
출력
True
복잡도 분석
정렬에 O(n log n)의 시간이 소요되고, 이후 선형 탐색에 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. 추가 메모리 사용 없이 제자리 정렬을 활용하면 공간 복잡도는 O(1) 수준으로 유지할 수 있습니다.