파이썬(Python)으로 인접 요소 조건부 스왑을 활용해 배열 정렬 가능 여부 확인하기

문제 개요

0부터 n-1 범위의 숫자로 이루어진 정렬되지 않은 배열 nums가 있다고 가정해 보겠습니다. 우리는 인접한 두 요소의 절대값 차이가 정확히 1일 때에만 두 요소를 서로 교환(swap)할 수 있으며, 이러한 교환은 필요한 만큼 몇 번이든 반복할 수 있습니다. 이때 주어진 배열을 오름차순으로 정렬할 수 있는지 판별하는 것이 이 문제의 목표입니다.

예를 들어 입력이 nums = [1, 0, 3, 2, 5, 4]라고 해봅시다. (1, 0), (3, 2), (5, 4) 쌍을 각각 교환하면 [0, 1, 2, 3, 4, 5]로 정렬할 수 있으므로 출력 결과는 True가 됩니다.

해결 접근 방법

핵심 아이디어는 간단합니다. 스왑이 허용되는 유일한 경우는 두 인접 요소의 차이가 1인 경우뿐이므로, 순서가 어긋난 두 인접 요소의 차이가 1보다 크다면 어떤 조합의 스왑을 사용해도 상대적 순서를 바로잡을 수 없습니다. 따라서 배열을 왼쪽에서 오른쪽으로 한 번만 순회하면 답을 구할 수 있습니다.

• 인덱스 i를 0부터 (배열 길이 - 2)까지 순회합니다.
• 만약 nums[i] > nums[i+1]이라면:
  • nums[i] - nums[i+1] == 1이면 두 요소를 서로 교환합니다.
  • 그렇지 않으면 더 이상 정렬이 불가능하므로 즉시 False를 반환합니다.

모든 순회가 끝날 때까지 위 조건에 걸리지 않았다면 배열을 정렬할 수 있는 것이므로 True를 반환합니다.

예제 코드

다음 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.

def solve(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i+1]:
            if nums[i] - nums[i+1] == 1:
                nums[i], nums[i+1] = nums[i+1], nums[i]
            else:
                return False
    return True

nums = [1, 0, 3, 2, 5, 4]
print(solve(nums))

입력

[1, 0, 3, 2, 5, 4]

출력

True

복잡도 분석

이 알고리즘은 배열을 단 한 번 순회하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간 없이 제자리(in-place)에서 동작하기 때문에 공간 복잡도는 O(1)입니다. 배열의 길이가 커져도 효율적으로 동작하는 장점이 있습니다.