문제 개요
모든 요소가 서로 다른(고유한) 숫자 배열 nums가 주어졌을 때, 이 배열이 거의 정렬된(almost sorted) 상태인지 확인하는 문제입니다.
여기서 '거의 정렬됨'이란, 배열을 완전히 정렬했을 때 각 요소가 자신의 원래 위치에서 최대 1칸까지만 벗어나 있음을 의미합니다.
예를 들어 입력이 nums = [10, 30, 20, 40]이라면 결과는 True입니다. 10은 이미 제자리에 있고, 30과 20은 서로 한 칸씩만 어긋나 있으며, 40 역시 올바른 위치에 있기 때문입니다.
접근 방법
핵심 아이디어는 인접한 두 요소를 비교하여 순서가 어긋난 경우 한 번씩 교환(swap)해 주는 것입니다. 요소가 최대 한 칸만 벗어났다면, 인접 요소와의 단 한 번의 교환만으로 제자리로 돌아갈 수 있습니다. 교환 단계를 모두 마친 뒤 배열을 다시 훑어 보았을 때 여전히 내림차순 쌍이 남아 있다면, 그 배열은 거의 정렬된 상태가 아닌 것입니다.
알고리즘의 진행 순서는 다음과 같습니다.
i를 0으로 초기화합니다.i가 배열 길이 - 1보다 작은 동안 다음을 반복합니다.nums[i] > nums[i + 1]이면 두 요소를 교환하고i를 하나 더 증가시킵니다.i를 1 증가시킵니다.
- 배열 전체를 다시 순회하면서
nums[i] > nums[i + 1]인 구간이 발견되면False를 반환합니다. - 모든 검사를 통과하면
True를 반환합니다.
구현 예제
다음 파이썬 코드로 위 알고리즘을 구현할 수 있습니다.
def solve(nums):
i = 0
while i < len(nums) - 1:
if nums[i] > nums[i + 1]:
nums[i], nums[i + 1] = nums[i + 1], nums[i]
i += 1
i += 1
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return False
return True
nums = [10, 30, 20, 40]
print(solve(nums))
입력
[10, 30, 20, 40]
출력
True
동작 과정 살펴보기
입력 [10, 30, 20, 40]에 대해 첫 번째 패스가 어떻게 진행되는지 단계별로 확인해 보겠습니다.
- i = 0: 10 < 30이므로 교환하지 않습니다.
- i = 1: 30 > 20이므로 두 요소를 교환합니다. 배열은
[10, 20, 30, 40]이 되고,i는 한 번에 2만큼 증가합니다. - i = 3: 반복 조건을 만족하지 않으므로 루프가 종료됩니다.
이후 두 번째 순회에서 모든 인접 쌍이 오름차순임을 확인하고 최종적으로 True를 반환합니다.
복잡도 분석
- 시간 복잡도: 배열을 최대 두 번 순회하므로 O(n)입니다.
- 공간 복잡도: 추가 메모리 없이 제자리(in-place)에서 처리하므로 O(1)입니다.