파이썬으로 전체 정렬을 만들 수 있는 최대 하위 리스트 분할 개수 구하기

숫자 리스트 nums가 주어졌다고 가정해 보겠습니다. 이 리스트를 여러 개의 개별 하위 리스트(조각)로 나눈 뒤, 각 조각을 따로 정렬할 수 있습니다. 이때 구해야 하는 것은, 분할 후 각 조각을 정렬했을 때 nums 전체가 정렬된 상태가 되도록 만들 수 있는 하위 리스트의 최대 개수입니다.

예시

예를 들어 입력이 nums = [4, 3, 2, 1, 7, 5]라면 출력은 2가 됩니다. 리스트를 [4, 3, 2, 1]과 [7, 5] 두 개의 하위 리스트로 나누어 각각 정렬하면 [1, 2, 3, 4]와 [5, 7]이 되어, 이어 붙였을 때 전체가 정렬되기 때문입니다.

해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다:

• count := 0으로 초기화합니다.
• main_sum := 0, sorted_sum := 0으로 초기화합니다.
• 원본 리스트 nums의 각 원소 x와 정렬된 리스트의 각 원소 y에 대해 반복합니다:
  • main_sum := main_sum + x
  • sorted_sum := sorted_sum + y
  • 만약 main_sum과 sorted_sum이 같다면:
    • count := count + 1
• count를 반환합니다.

동작 원리

핵심 아이디어는 접두사 합(prefix sum) 비교입니다. 어떤 인덱스 k까지의 원본 리스트 합과 정렬된 리스트 합이 서로 같다면, 그 앞부분 원소들은 전체에서 가장 작은 k개의 값들과 정확히 동일한 집합이라는 의미입니다. 즉, 해당 지점에서 리스트를 잘라도 앞부분만 정렬하면 뒷부분과 섞일 필요가 없으므로 안전한 '분할 지점'이 됩니다. 이러한 지점의 개수를 세면 곧 최대 분할 개수가 됩니다.

구현 예제

더 잘 이해하기 위해 다음 파이썬 구현을 살펴보겠습니다:

class Solution:
   def solve(self, nums):
      count = 0
      main_sum = sorted_sum = 0

      for x, y in zip(nums, sorted(nums)):
         main_sum += x
         sorted_sum += y
         if main_sum == sorted_sum:
            count += 1

      return count

ob = Solution()
nums = [4, 3, 2, 1, 7, 5]
print(ob.solve(nums))

입력

[4, 3, 2, 1, 7, 5]

출력

2

이 알고리즘은 리스트를 한 번 순회하고 정렬에 O(n log n)이 필요하므로, 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 정렬된 복사본 저장을 위해 O(n)입니다.