Python으로 배열이 1부터 n까지 자연수의 회전 형태인지 확인하는 방법

숫자 리스트 nums가 주어졌을 때, 이 리스트를 오른쪽으로 원하는 횟수만큼 회전시켜 [1, 2, ..., n] 또는 [n, n-1, ..., 1]처럼 첫 n개의 자연수가 증가하거나 감소하는 형태로 만들 수 있는지 확인해야 합니다.

예를 들어 입력이 nums = [5, 6, 1, 2, 3, 4]라면 결과는 True입니다. 리스트를 네 번 오른쪽으로 회전하면 [1, 2, 3, 4, 5, 6]이 되기 때문입니다.

해결 접근 방법

이 문제는 인접한 두 요소 사이의 차이를 검사하는 방식으로 해결할 수 있습니다. 올바르게 회전된 연속 자연수 배열에서는 모든 인접 요소의 차이가 반드시 1 또는 n-1이어야 합니다. 차이가 n-1이 되는 경우는 배열의 끝과 시작이 이어지는 경계 지점(예: ... 4, 5, 6, 1 ...)에 해당합니다.

알고리즘은 다음과 같습니다.

• n := nums의 크기
• i를 1부터 n-1까지 반복:
  • |nums[i-1] - nums[i]|가 1도 아니고 n-1도 아니라면 False 반환
• 모든 검사를 통과하면 True 반환

예제 코드

def solve(nums):
    n = len(nums)
    for i in range(1, n):
        if abs(nums[i - 1] - nums[i]) != 1 and abs(nums[i - 1] - nums[i]) != n - 1:
            return False
    return True

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

입력

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

출력

True

동작 원리 정리

위 코드는 리스트 전체를 한 번씩 훑으면서 인접 요소 간 차이만 확인하기 때문에 시간 복잡도는 O(n)입니다. 배열을 실제로 회전시켜 가며 비교하는 것보다 훨씬 효율적이며, 어떤 회전 상태에서든 연속된 자연수 배열이라면 인접 차이가 항상 1 또는 n-1을 유지한다는 성질을 활용합니다.