Python으로 배열 정렬을 위해 제거해야 하는 가장 짧은 하위 배열 찾기

문제 개요

배열 arr가 주어졌을 때, 배열에서 하나의 연속된 하위 배열(subarray)을 제거하여 남은 원소들이 비내림차순(non-decreasing order), 즉 왼쪽에서 오른쪽으로 갈수록 값이 감소하지 않는 순서가 되도록 만들어야 합니다. 이때 제거해야 하는 가장 짧은 하위 배열의 길이를 구하는 것이 이 문제의 목표입니다.

예를 들어 입력이 arr = [10, 20, 30, 100, 40, 20, 30, 50]이라면 결과는 3입니다. 가운데의 [100, 40, 20] 부분만 제거하면 남은 원소들은 [10, 20, 30, 30, 50]처럼 비내림차순으로 정렬되며, 이보다 짧은 길이의 제거로는 정렬 상태를 만들 수 없기 때문입니다.

알고리즘 접근 방식

이 문제는 양쪽 끝에서부터 각각 정렬된 구간을 확장해 나가는 투 포인터(two pointer) 기법으로 효율적으로 해결할 수 있습니다. 왼쪽에서 출발하는 포인터 p와 오른쪽에서 출발하는 포인터 q를 활용해, 정렬된 접두사(prefix)와 접미사(suffix)를 최대한 길게 유지하면서 중간에 제거해야 할 구간의 길이를 최소화합니다.

구체적인 해결 단계는 다음과 같습니다:

n := 배열 arr의 크기
arr := 배열 맨 앞에 0을, 맨 뒤에 무한대(infinity)를 삽입 (경계 조건 처리를 단순화하기 위함)
A, B := 두 개의 새로운 빈 리스트 (왼쪽 정렬 구간과 오른쪽 정렬 구간을 저장)
p := 1, q := 배열 크기 - 2
M := 0 (정렬 상태로 유지할 수 있는 최대 원소 개수)
p <= q인 동안 반복:
- arr[p-1] <= arr[p]이면 → A의 끝에 arr[p]를 추가하고 p를 1 증가
- 그렇지 않고 arr[q] <= arr[q+1]이면 → B의 끝에 arr[q]를 추가한 뒤, A가 비어 있지 않고 A의 마지막 원소가 B의 마지막 원소보다 큰 동안 A에서 마지막 원소를 삭제하고, q를 1 감소
- 위 두 조건 모두 해당하지 않으면 → 반복문 탈출
매 반복마다 M := M과 (A의 크기 + B의 크기) 중 최댓값으로 갱신
최종적으로 n - M을 반환 (전체 길이에서 정렬 가능한 최대 길이를 뺀 값 = 제거해야 할 최소 길이)

Python 구현 예제

아래 코드를 통해 실제 구현 과정을 확인할 수 있습니다.

def solve(arr):
   n = len(arr)
   arr = [0] + arr + [float("inf")]
   A,B=[],[]
   p,q=1,len(arr)-2
   M = 0
   while p <= q:
      if arr[p-1] <= arr[p]:
         A.append(arr[p])
         p += 1
      elif arr[q] <= arr[q+1]:
         B.append(arr[q])
         while A and A[-1] > B[-1]:
            A.pop()
         q -= 1
      else:
         break
      M = max(M, len(A)+len(B))
   return n - M

arr = [10,20,30,100,40,20,30,50]
print(solve(arr))

입력

[10,20,30,100,40,20,30,50]

출력

복잡도 분석

이 알고리즘은 두 포인터가 배열을 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 배열 전체를 정렬하는 방식(O(n log n))보다도 효율적이며, 추가로 사용하는 공간 역시 선형 수준으로 제한적이므로 대규모 입력에서도 안정적인 성능을 기대할 수 있습니다.