숫자로 이루어진 리스트 nums가 주어졌을 때, 회전(rotation) 연산만 사용해서 이 배열을 정렬할 수 있는지 확인해야 합니다. 여기서 회전이란 배열의 끝부분에 있는 연속된 요소들을 잘라내어 배열 맨 앞으로 가져오는 작업을 의미합니다.
예를 들어 입력이 nums = [4,5,6,1,2,3]이라면 결과는 True입니다. 마지막 세 요소(1, 2, 3)를 앞쪽으로 회전시키면 [1,2,3,4,5,6]이 되어 완전히 정렬된 배열을 얻을 수 있기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다:
- n := nums의 크기
- nums가 이미 정렬되어 있다면 True를 반환
- 그렇지 않다면:
- status := True로 초기화
- i를 0부터 n-2까지 순회하면서 처음으로 nums[i] > nums[i+1]이 되는 지점(감소 지점)을 찾으면 반복 중단
- i := i + 1
- k를 i부터 n-2까지 순회하면서 다시 감소 지점이 발견되면 status := False로 설정하고 반복 중단
- status가 False라면 False를 반환 (감소 지점이 두 번 이상 나타나면 회전으로 정렬 불가)
- 그렇지 않다면 nums[n-1] <= nums[0]일 때 True를 반환하고, 아니면 False를 반환
예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다:
def solve(nums):
n = len(nums)
if all(nums[i] <= nums[i + 1] for i in range(len(nums) - 1)):
return True
else:
status = True
for i in range(n - 1):
if nums[i] > nums[i + 1]:
break
i += 1
for k in range(i, n - 1):
if nums[k] > nums[k + 1]:
status = False
break
if not status:
return False
else:
if nums[n - 1] <= nums[0]:
return True
return False
nums = [4,5,6,1,2,3]
print(solve(nums))
입력
[4,5,6,1,2,3]
출력
True
동작 원리
핵심 아이디어는 간단합니다. 회전만으로 정렬할 수 있는 배열은 최대 한 번의 감소 지점만 가집니다. 즉, 배열이 오름차순으로 증가하다가 한 번 꺾인 뒤 다시 오름차순으로 이어져야 하고, 마지막 요소가 첫 번째 요소보다 작거나 같아야 합니다. 이 조건을 만족하면 꺾인 지점을 기준으로 회전하여 전체 배열을 정렬할 수 있습니다. 시간 복잡도는 O(n)으로 매우 효율적입니다.