문제 개요
배열 nums가 주어졌을 때, 이 배열이 원래 비내림차순(non-decreasing)으로 정렬되어 있다가 일정 횟수(0회 포함)만큼 회전된 상태인지 확인해야 합니다. 배열에는 중복된 값이 존재할 수도 있습니다.
예를 들어 입력이 nums = [12,15,2,5,6,9]라면, 이 배열은 정렬된 상태 [2,5,6,9,12,15]에서 오른쪽으로 두 칸 회전된 것이므로 결과는 True가 됩니다.
해결 접근 방법
핵심 아이디어는 다음과 같습니다. 먼저 배열에서 오름차순이 유지되는 지점까지 탐색한 뒤, 그 지점을 기준으로 배열을 잘라 순서를 바꿔 연결하면 원래의 정렬된 배열이 복원됩니다. 복원된 배열 전체가 비내림차순이라면 주어진 배열은 '정렬 후 회전'된 배열입니다.
j = 0으로 초기화합니다.j가 배열 길이 - 1보다 작고nums[j] <= nums[j + 1]인 동안j를 1씩 증가시켜, 오름차순이 끊기는 위치를 찾습니다.res = nums[j+1:] + nums[:j+1]로 두 부분 배열을 연결하여 회전을 되돌린 배열을 만듭니다.res를 순회하면서 인접한 두 원소 중 앞의 값이 더 큰 경우가 있으면 False를 반환합니다.- 끝까지 문제가 없으면 True를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 동작을 확인할 수 있습니다.
def solve(nums):
j = 0
while (j < len(nums) - 1 and nums[j] <= nums[j + 1]):
j += 1
res = nums[j + 1 : len(nums)] + nums[0:j + 1]
for i in range(len(res) - 1):
if res[i] > res[i + 1]:
return False
return True
nums = [12,15,2,5,6,9]
print(solve(nums))입력
[12,15,2,5,6,9]
출력
True
동작 원리와 시간 복잡도
위 예제에서 첫 번째 while 루프는 15 → 2로 감소하는 지점에서 멈추므로 j = 1이 됩니다. 이후 배열을 [2,5,6,9]와 [12,15]로 나누어 뒤집어 연결하면 [2,5,6,9,12,15], 즉 완전히 정렬된 배열이 얻어집니다. 따라서 최종 결과는 True입니다.
이 알고리즘은 배열을 한두 번 순회하므로 시간 복잡도는 O(n), 새로운 배열 res를 만들기 때문에 공간 복잡도 역시 O(n)입니다. 참고로 추가 배열 없이 '감소 지점(순환점)'의 개수만 세는 방식으로 O(1) 공간에도 해결할 수 있습니다. 배열을 한 번만 순회하며 이전 원소보다 작아지는 지점의 개수를 세고, 그 개수가 1 이하이며 마지막 원소가 첫 번째 원소보다 크지 않다면 조건을 만족하는 것입니다.