Python으로 리스트의 모든 값을 동일하게 만드는 최소 연산 횟수 계산하기

문제 개요

정수로 이루어진 리스트 nums가 주어집니다. 우리는 다음과 같은 연산을 수행할 수 있습니다.

• 리스트에서 가장 큰 숫자를 하나 골라, 두 번째로 큰 숫자와 같은 값으로 바꿉니다.

목표는 이 연산을 반복하여 리스트의 모든 정수를 동일하게 만드는 것이며, 이때 필요한 최소 연산 횟수를 반환해야 합니다.

예시

입력이 nums = [5, 9, 2]라고 가정해 보겠습니다. 이때 출력은 3입니다.

1. 먼저 9를 선택해 5로 바꿉니다 → [5, 5, 2]
2. 그다음 5를 선택해 2로 바꿉니다 → [5, 2, 2]
3. 마지막으로 남은 5를 2로 바꿉니다 → [2, 2, 2]

총 3번의 연산으로 모든 값이 2로 일치하게 됩니다.

접근 방법

핵심 아이디어는 간단합니다. 모든 값은 결국 리스트의 최솟값으로 수렴해야 하며, 각 원소는 자신보다 작은 고유한 값의 개수만큼 "단계"를 내려와야 합니다. 한 번의 연산으로 정확히 한 단계씩 내려올 수 있으므로, 각 원소에 필요한 연산 횟수를 모두 더하면 정답이 됩니다.

이를 위해 다음 단계를 따릅니다.

• vals: nums에서 중복을 제거한 고유한 값들을 오름차순으로 정렬한 리스트
• vtoi: vals의 각 값 v를 키로, 해당 인덱스 i를 값으로 갖는 맵(딕셔너리)
• nums의 모든 원소 v에 대해 vtoi[v]의 합을 반환

정렬된 고유값 리스트에서의 인덱스는 곧 "그 값 아래에 있는 서로 다른 값의 개수"를 의미합니다. 따라서 이 인덱스들의 합이 곧 최소 연산 횟수가 됩니다.

구현 예제

class Solution:
    def solve(self, nums):
        vals = sorted(set(nums))
        vtoi = {v: i for i, v in enumerate(vals)}
        return sum(vtoi[v] for v in nums)

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

입력

[5, 9, 2]

출력

3

복잡도 분석

고유값을 정렬하는 데 O(n log n)의 시간이 소요되며, 이후 합을 구하는 과정은 O(n)입니다. 따라서 전체 시간 복잡도는 O(n log n), 공간 복잡도는 O(n)입니다.