문제 개요
정수 배열이 하나 주어졌을 때, 배열 안에서 연속된 하나의 부분 배열을 골라 그 부분만 오름차순으로 정렬했을 때 전체 배열이 완전히 정렬되도록 만드는, 가장 짧은 부분 배열을 찾아야 합니다. 최종적으로 그 부분 배열의 길이를 출력하면 됩니다.
예를 들어 배열이 [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의 길이 - 1까지 반복하면서,nums[i]와res[i]가 다르면 인덱스i를r에 추가합니다.반복이 끝난 후
r가 비어 있다면 배열이 이미 정렬되어 있는 것이므로 0을 반환합니다.그렇지 않다면
r의 마지막 원소에서 첫 번째 원소를 뺀 값에 1을 더한 값, 즉r[-1] - r[0] + 1을 반환합니다. 이것이 정렬해야 할 가장 짧은 연속 구간의 길이입니다.
예제 코드 (Python)
다음 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
class Solution(object):
def findUnsortedSubarray(self, nums):
res = sorted(nums)
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
동작 설명
위 예제에서 정렬된 배열은 [2,4,6,8,9,10,15]입니다. 원본 배열과 비교하면 인덱스 1(6↔4), 2(4↔6), 4(10↔9), 5(9↔10)에서 값이 서로 다릅니다. 따라서 r = [1, 2, 4, 5]가 되고, 정답은 5 - 1 + 1 = 5로 계산됩니다.
참고로 배열이 이미 정렬되어 있는 경우에는 서로 다른 인덱스가 존재하지 않으므로 함수는 0을 반환합니다. 또한 두 위치의 값만 맞바뀐 경우처럼 단 하나의 인덱스만 어긋나는 상황은 실제로 발생하지 않지만, 코드에서는 안전하게 처리하고 있습니다.
복잡도 분석
시간 복잡도: O(n log n) — 배열 정렬 과정이 지배적이며, 이후의 비교와 탐색은 O(n)입니다.
공간 복잡도: O(n) — 정렬된 복사본
res와 인덱스 리스트r를 추가로 저장합니다.