문제 개요
크기가 n인 정렬되지 않은 배열 A[0..n-1]이 주어졌다고 가정해 보겠습니다. 우리는 이 배열에서 최소 길이의 연속된 하위 배열 A[s..e]를 찾아야 합니다. 이 하위 배열만 정렬하면 전체 배열이 오름차순으로 정렬됩니다.
예를 들어, 배열이 [2,6,4,8,10,9,15]라고 한다면 출력은 5가 됩니다. 정렬해야 하는 하위 배열은 [6,4,8,10,9]입니다. 이 부분만 정렬하면 전체 배열이 [2,4,6,8,9,10,15]로 완전히 정렬되기 때문입니다.
해결 접근 방법
이 문제는 간단한 비교 방식으로 해결할 수 있습니다. 원본 배열과 정렬된 배열을 요소별로 비교하여, 서로 다른 값들이 나타나는 가장 앞선 인덱스와 가장 뒤의 인덱스 사이의 길이를 계산하면 됩니다.
구체적인 풀이 단계는 다음과 같습니다:
- res := 주어진 배열 nums를 정렬한 새로운 배열
- r := 불일치 인덱스를 저장할 빈 리스트
- i를 0부터 res의 길이까지 반복하면서:
- nums[i]와 res[i]가 다르면 i를 r에 추가
- r의 길이가 0이면 0을 반환 (배열이 이미 정렬된 상태)
- r의 길이가 1이면 1을 반환
- 그 외의 경우에는 (r의 마지막 요소 - r의 첫 번째 요소 + 1)을 반환
예제 코드
더 나은 이해를 위해 다음 파이썬 구현을 살펴보겠습니다:
class Solution(object):
def findUnsortedSubarray(self, nums):
res = sorted(nums)
ans = 0
r = []
for i in range(len(res)):
if nums[i] != res[i]:
r.append(i)
if not len(r):
return 0
if len(r) == 1:
return 1
return r[-1]-r[0]+1
ob1 = Solution()
print(ob1.findUnsortedSubarray([2,6,4,8,10,9,15]))입력
[2,6,4,8,10,9,15]
출력
5
동작 원리 설명
위 코드에서 먼저 sorted(nums)를 통해 배열을 정렬한 기준 배열(res)을 만듭니다. 그다음 원본 배열과 기준 배열을 인덱스별로 비교하면서 값이 일치하지 않는 모든 위치를 리스트 r에 저장합니다.
불일치가 발생한 인덱스 중 가장 작은 값(첫 번째 요소)부터 가장 큰 값(마지막 요소)까지가 바로 정렬이 필요한 구간입니다. 따라서 두 인덱스의 차이에 1을 더한 값이 곧 정렬해야 하는 최소 하위 배열의 길이가 됩니다.
시간 및 공간 복잡도
이 알고리즘은 배열 정렬에 O(n log n), 요소 비교에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 정렬된 배열과 인덱스 리스트를 저장해야 하므로 O(n)입니다.