Python으로 배열을 연속된 요소 간 차이가 같도록 재배열할 수 있는지 확인하는 프로그램

리스트 nums가 주어졌을 때, 이 리스트의 순서를 재배열하여 연속된 두 숫자의 차이가 항상 동일하도록 만들 수 있는지 확인하는 문제입니다. 즉, 배열이 등차수열 형태가 될 수 있는지를 판별하는 것입니다.

문제 예시

예를 들어 입력이 nums = [8, 2, 6, 4]라면 결과는 True입니다. 왜냐하면 이 배열을 [2, 4, 6, 8]과 같이 재배열하면, 연속된 두 숫자의 차이가 모두 2로 동일하기 때문입니다.

해결 접근 방법

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

• 먼저 N을 nums의 크기(길이)로 설정합니다.
• N이 2 이하라면 어떤 순서든 조건을 만족하므로 True를 반환합니다.
• 리스트 nums를 오름차순으로 정렬합니다.
• 정렬 후 첫 번째와 두 번째 요소의 차이를 목표 차이(targetDiff)로 지정합니다.
• 세 번째 요소부터 마지막 요소까지 반복하면서, 인접한 두 요소의 차이가 targetDiff와 다르면 False를 반환합니다.
• 모든 검사를 통과하면 True를 반환합니다.

핵심 아이디어는 간단합니다. 배열을 정렬했을 때 모든 인접 요소의 차이가 일정하다면 그 배열은 등차수열이 되며, 정렬되지 않은 원래 배열은 언제나 이 순서로 재배열될 수 있기 때문에 정렬 기반 검사만으로 충분합니다.

구현 예제 코드

아래의 Python 구현을 통해 더 잘 이해할 수 있습니다.

def solve(nums):
    N = len(nums)
    if N <= 2:
        return True
    nums.sort()
    targetDiff = nums[1] - nums[0]
    for i in range(2, N):
        if nums[i] - nums[i - 1] != targetDiff:
            return False
    return True

nums = [8, 2, 6, 4]
print(solve(nums))

입력

[8, 2, 6, 4]

출력

True

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 정렬 과정이 지배적이므로 O(N log N)입니다. 정렬 이후의 선형 검사는 O(N)이지만 전체 복잡도에는 큰 영향을 주지 않습니다. 공간 복잡도는 추가 메모리를 거의 사용하지 않으므로 O(1)입니다(Python의 내장 정렬은 최악의 경우 O(N) 공간을 사용할 수 있습니다).