중복 없는 고유한 요소로 이루어진 배열 nums가 주어졌다고 가정해 보겠습니다. 이 배열에서 단 하나의 하위 배열(sub-array)만 뒤집어서 전체 배열을 오름차순으로 정렬할 수 있는지 확인해야 합니다. 배열이 이미 정렬되어 있다면 뒤집을 필요가 없으므로 역시 true를 반환합니다.
예를 들어 입력이 nums = [4,6,27,25,15,9,37,42]라고 해보겠습니다. 가운데 [9,15,25,27] 구간을 뒤집으면 [4,6,9,15,25,27,37,42]가 되어 배열 전체가 정렬되므로 출력은 True입니다.
문제 해결 접근 방법
이 문제의 핵심은 배열을 왼쪽에서 오른쪽으로 훑으며 처음으로 순서가 어긋나는 지점을 찾는 것입니다. 그 지점부터 이어지는 내림차순 구간이 바로 뒤집어야 할 하위 배열이며, 뒤집은 결과가 앞뒤 요소와 자연스럽게 이어지는지, 나머지 구간이 여전히 오름차순을 유지하는지만 추가로 검증하면 됩니다. 구체적인 단계는 다음과 같습니다.
- n := nums의 크기
- 배열에 요소가 하나뿐이면 True를 반환합니다.
- i := 1로 초기화합니다.
- i를 1부터 n-1까지 반복합니다.
- nums[i-1] < nums[i]이면 아직 오름차순이 유지되고 있는 것이므로 계속 진행하고, i가 n에 도달하면 true를 반환합니다.
- nums[i-1] >= nums[i]라면 순서가 어긋나기 시작한 지점이므로 반복문을 빠져나옵니다.
- j := i로 설정합니다.
- j < n이고 nums[j] < nums[j-1]인 동안 다음을 반복합니다.
- i > 1이고 nums[j] < nums[i-2]이면 false를 반환합니다. 뒤집을 구간의 최솟값이 바로 앞 요소보다 작아 어떻게 뒤집어도 정렬이 불가능하기 때문입니다.
- j := j + 1
- j가 n과 같으면 True를 반환합니다. 내림차순 구간이 배열 끝까지 이어진다는 의미입니다.
- k := j로 설정합니다.
- nums[k] < nums[i-1]이면 False를 반환합니다. 뒤집힌 구간의 최댓값이 그 뒤 요소보다 커서 정렬이 깨지기 때문입니다.
- k > 1이고 k < n인 동안 다음을 반복합니다.
- nums[k] < nums[k-1]이면 False를 반환합니다.
- k := k + 1
- 모든 검증을 통과했다면 True를 반환합니다.
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
def solve(nums):
n = len(nums)
if n == 1:
return True
i = 1
for i in range(1, n):
if nums[i - 1] < nums[i]:
if i == n:
return True
else:
break
j = i
while j < n and nums[j] < nums[j - 1]:
if i > 1 and nums[j] < nums[i - 2]:
return False
j += 1
if j == n:
return True
k = j
if nums[k] < nums[i - 1]:
return False
while k > 1 and k < n:
if nums[k] < nums[k - 1]:
return False
k += 1
return True
nums = [4,6,27,25,15,9,37,42]
print(solve(nums))
입력
[4,6,27,25,15,9,37,42]
출력
True
복잡도 및 정리
이 알고리즘은 배열을 한 번만 순회하고 몇 개의 변수만 사용하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 정렬되지 않은 부분이 정확히 하나의 연속된 내림차순 구간이고, 그 양 끝이 앞뒤 요소와 올바르게 맞물리는지만 확인하면 되기 때문에 실제로 뒤집기를 수행하지 않고도 답을 판별할 수 있다는 점이 이 풀이의 장점입니다.