Python에서 배열이 정렬 후 회전된 상태인지 확인하는 방법

서로 다른 고유한 값 n개로 이루어진 배열이 있다고 가정해 봅시다. 우리가 확인해야 할 것은 이 배열이 정렬된 후 회전된 상태인지 여부입니다. 단, 최소 한 번의 회전이 반드시 필요하기 때문에 완전히 정렬만 된 배열은 정렬·회전 상태로 간주하지 않습니다.

예를 들어 입력이 nums = [4,5,6,8,1,3]이라면 출력은 True가 됩니다. 시계 방향으로 두 번 회전하면 [1, 3, 4, 5, 6, 8]처럼 정렬된 형태가 되기 때문입니다.

문제 해결 접근법

다음 단계를 따라 문제를 해결할 수 있습니다.

• min_element := 배열 nums의 최솟값
• min_index := nums에서 min_element가 위치한 인덱스
• before_sorted := True로 초기화
• i가 1부터 min_index - 1까지일 때: nums[i] < nums[i-1]이면 before_sorted := False로 설정하고 반복 종료
• after_sorted := True로 초기화
• i가 min_index + 1부터 배열 길이 - 1까지일 때: nums[i] < nums[i-1]이면 after_sorted := False로 설정하고 반복 종료
• before_sorted와 after_sorted가 모두 참이면서, 배열의 마지막 원소가 nums[0]보다 작으면 True 반환
• 그렇지 않으면 False 반환

구현 예제

아래 예제 코드를 통해 더 잘 이해해 봅시다.

def solve(nums):
    min_element = min(nums)
    min_index = nums.index(min_element)

    before_sorted = True
    for i in range(1, min_index):
        if nums[i] < nums[i - 1]:
            before_sorted = False
            break

    after_sorted = True
    for i in range(min_index + 1, len(nums)):
        if nums[i] < nums[i - 1]:
            after_sorted = False
            break

    if before_sorted and after_sorted and nums[-1] < nums[0]:
        return True
    else:
        return False

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

실행 결과

입력:

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

출력:

True

동작 원리와 복잡도

정렬 후 회전된 배열에는 최댓값 바로 다음에 최솟값이 오는 회전 지점이 단 하나만 존재합니다. 따라서 최솟값을 기준으로 앞 구간과 뒷 구간이 각각 오름차순을 유지하고, 마지막 원소가 첫 번째 원소보다 작다면(실제 회전이 일어났다는 의미) 해당 배열을 정렬 후 회전된 상태로 판단할 수 있습니다.

이 알고리즘은 배열을 최대 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용량은 O(1)입니다.