파이썬으로 숫자 리스트를 오름차순 또는 내림차순으로 정렬할 때 필요한 최소 비용 구하기

숫자 리스트 nums가 주어졌을 때, 이 리스트를 오름차순 또는 내림차순 중 어느 방향으로든 정렬하는 데 드는 최소 비용을 구하는 문제입니다. 여기서 비용이란 각 요소의 기존 값과 새로운 값 사이 차이의 절댓값을 모두 더한 합을 의미합니다.

예를 들어 입력이 [2, 5, 4]라면 출력은 2가 됩니다.

문제 해결 접근 방식

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

• 원본 배열 nums의 복사본 temp를 만듭니다.
• temp 리스트를 오름차순으로 정렬합니다.
• 비용 변수 c1과 c2를 0으로 초기화합니다.
• n은 배열 nums의 크기입니다.
• i를 0부터 n-1까지 반복하면서 다음을 수행합니다.
  • nums[i]가 temp[i]와 다르면, c1 += |nums[i] - temp[i]|를 누적합니다. (오름차순 정렬 비용)
  • nums[i]가 temp[n-1-i]와 다르면, c2 += |nums[i] - temp[n-i-1]|를 누적합니다. (내림차순 정렬 비용)
• 최종적으로 c1과 c2 중 더 작은 값을 반환합니다.

핵심 아이디어는 정렬된 배열과 역순으로 정렬된 배열을 각각 원본과 비교하여, 두 경우 중 비용이 더 적은 쪽을 선택하는 것입니다.

구현 예제

class Solution:
    def solve(self, nums):
        temp = nums.copy()
        temp.sort()
        c1 = 0
        c2 = 0
        n = len(nums)
        for i in range(n):
            if nums[i] != temp[i]:
                c1 += abs(nums[i] - temp[i])
            if nums[i] != temp[n-1-i]:
                c2 += abs(nums[i] - temp[n-i-1])
        return min(c1, c2)

ob = Solution()
print(ob.solve([2, 5, 4]))

입력

[2, 5, 4]

출력

2

동작 원리 설명

입력 [2, 5, 4]의 경우를 살펴보겠습니다.

• 오름차순 정렬 결과는 [2, 4, 5]이며, 이때 비용 c1은 |4-5| = 1입니다.
• 내림차순 정렬 결과는 [5, 4, 2]이며, 이때 비용 c2는 |2-5| + |4-4| + |4-2| = 3 + 0 + 2 = 5입니다.

두 비용 중 최솟값인 2... 즉, 오름차순 정렬 시 발생하는 비용 1과 내림차순 정렬 시 발생하는 비용을 비교하여 더 작은 값이 최종 결과로 반환됩니다. 이 알고리즘의 시간 복잡도는 정렬에 의해 지배되므로 O(n log n)입니다.