배열의 전체 원소들이 연속되게 만들 수 있게 원소의 수를 바꾸는 최소 횟수를 구하는 문제.

Solution

먼저 순서가 상관이 없으므로 정렬을 하고 시작하자.

그러면 뭔가 보이는데, 만약 결과 배열의 시작을 a 로 잡았다면 결과 배열은 [a, a+1, a+2 ... a + n-1] 이 된다. 여기서 힌트를 얻어 주어진 배열에서 임의의 원소를 시작으로 잡는 결과 배열을 얻을 수 있고 이렇게 만들 수 있는 최소 횟수를 구할 수 있다.

계산을 쉽게 하기 위해 중복되는 원소는 제거한다. (중복되는 값은 무조건 바꿔야 되므로 쓰레기 값으로 가정한다고 생각하면 된다) 그리고 결과 배열을 만들기 위해 바꿔야 되는 횟수를 이분 탐색으로 구해주면 된다.

예를 들어 1, 2, 5, 6 에서 1, 2, 3, 4로 바꿔야 하는 횟수는 4보다 큰 수를 다 바꿔줘야 하는데, 4에 대해 이분 탐색으로 찾은 뒤 이 뒤에 나온 원소들은 전부 바꿔줘야 한다.
2, 3, 4, 5로 바꾸는 횟수는 5보다 큰 수와 2 보다 작은 1을 임의의 수로 바꿔야 한다. 식을 정리하면 아래와 같다.

start = nums[i]
end = start + n - 1

idx = bisect.bisect_right(end, nums)
cnt = n - idx + i

아래 글 참고.
https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/discuss/1470853/Python-Binary-Search-Clean-and-Concise

Source Code

import bisect
from typing import List


class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        nums = sorted(set(nums))

        ans = 987654321

        for i in range(len(nums)):
            start = nums[i]
            end = start + n - 1

            idx = bisect.bisect_right(nums, end)
            ans = min(ans, n - idx + i)

        return ans

2009. Minimum Number of Operations to Make Array Continuous

Problem link

Problem Summary

Solution

Source Code