문제 개요
숫자로 이루어진 리스트 nums가 주어졌을 때, 이 리스트의 연속된 부분 구간(서브리스트) 하나만 정렬하면 전체 배열이 오름차순으로 정렬되는 가장 짧은 구간의 길이를 구하는 문제입니다.
예를 들어 입력이 nums = [1, 2, 5, 4, 9, 10]이라면 출력은 2입니다. [5, 4] 구간만 정렬하면 [1, 2, 4, 5, 9, 10]이 되어 전체 리스트가 정렬되기 때문입니다.
해결 접근 방법
핵심 아이디어는 간단합니다. 원본 리스트를 정렬한 결과와 요소별로 비교했을 때, 처음으로 달라지는 위치부터 마지막으로 달라지는 위치까지가 바로 정렬이 필요한 구간입니다. 다음 단계로 해결할 수 있습니다.
- 첫 번째 불일치 인덱스 f와 마지막 불일치 인덱스 l을 각각 -1로 초기화합니다.
- 원본 리스트 nums를 정렬한 복사본 lst를 만듭니다.
- 0부터 리스트 길이까지 반복하면서 nums[i]와 lst[i]를 비교합니다.
- 두 값이 다르면, 아직 f가 설정되지 않았다면(f == -1) f에 현재 인덱스를 저장하고, 그렇지 않으면 l에 현재 인덱스를 저장합니다.
- 반복이 끝난 후 f와 l이 모두 -1이라면 리스트가 이미 정렬되어 있는 것이므로 0을 반환합니다.
- 그 외의 경우에는 l - f + 1을 반환합니다. 이 값이 정렬이 필요한 최단 구간의 길이입니다.
구현 예제
class Solution:
def solve(self, nums):
f = -1
l = -1
lst = sorted(nums)
for i in range(len(nums)):
if nums[i] != lst[i]:
if f == -1:
f = i
else:
l = i
if l == -1 and f == -1:
return 0
return l - f + 1
ob = Solution()
print(ob.solve([1, 2, 5, 4, 9, 10]))입력
[1, 2, 5, 4, 9, 10]
출력
2
동작 원리와 복잡도
정렬된 리스트와 원본 리스트를 비교하면, 어긋나는 요소들은 항상 하나의 연속된 범위 안에 존재합니다. 첫 불일치 위치 f부터 마지막 불일치 위치 l 사이의 요소들만 서로 재배열하면 전체가 정렬되고, 그 바깥의 요소들은 이미 올바른 자리에 있기 때문입니다.
시간 복잡도는 정렬에 O(n log n), 비교에 O(n)이 소요되므로 전체적으로 O(n log n)이며, 정렬된 복사본을 위해 O(n)의 추가 공간이 필요합니다.