Minimum Difference Between Largest and Smallest Value in Three Moves

정수 배열 nums가 주어진다. 한 번의 행동으로 아무 원소 하나를 골라서 아무런 값으로 바꿀 수 있다. 이때, 최대 세 번 행동한 이후에 배열에서 가장 큰 값과 가장 작은 값의 차이 값의 최소값을 구하자.

배열의 길이는 1 ~ 100,000, 값은 \(-10^9 \sim 10^9\)이다.

예를 들어 [5,3,2,4]에 대해서는 [2, 2, 2, 2]로 바꾸면 최대값과 최소값이 같아져서 차이값은 0이 된다.

단계 별로 생각하기

일단 가장 작은 값과 가장 큰 값을 알아야 하니까 정렬은 필수적이다. 그 다음은 어떻게 접근해야 할까?

처음에 든 생각은, 중위값을 기준으로 가장 큰 값과 가장 작은 값을 비교해가면서 더 큰 차이가 나는 쪽을 중위값으로 바꾸면 되지 않을까? 였는데, 곧바로 반례를 찾을 수 있었다.

올바른 접근은 차근차근 단계 별로 생각하는 것이다. 문제의 조건인 최대 3번의 행동을 단계로 쪼개자.

만약 0번의 행동, 즉 한 번도 움직일 수 없다면, 가장 큰 값과 가장 작은 값의 차이 값의 최소 값은 그냥 최대 값에서 최소 값을 뺀 값이다. 파이썬 인덱스를 이용해서 표현하면 (정렬된 배열을 기준으로) diff(0, -1)이 된다.

만약 1번의 행동만 할 수 있다면? 딱 하나를 아무 값으로 바꿀 수 있으니까, 다음 중 더 작은 값일 것이다:

두 번째로 큰 값과 최소 값의 차이. 이를 파이썬 인덱스를 이용해서 diff(0, -2)으로 표기하자.
두 번째로 작은 값과 최대 값의 차이. 역시 이는 diff(1, -1)이 된다.

즉, 정렬된 배열을 기준으로 하나, 최대값을 빼던가 아니면 최소값을 빼던가 했을 때의 차이 중 더 작은 것이 답이 된다. 여기서 아무 값 으로 바꿀 수 있기 때문에 그냥 단순히 배열에서 삭제하는 걸로 이해해도 무방하다.

만약 2번의 행동이 가능하다면? 다음 중 최소일 것이다.

세 번째로 큰 값과 최소 값의 차이, 즉 diff(0, -3)
세 번째로 작은 값과 최대 값의 차이, 즉 diff(2, -1)
두 번째로 큰 값과 두 번째로 작은 값의 차이, 즉 diff(1, -2)

따라서, 문제의 조건인 3번의 행동이 가능하다면, 다음 값 중 최소일 것이다:

네 번째로 큰 값과 최소 값의 차이, diff(0, -4)
세 번째로 큰 값과 두 번째로 작은 값의 차이, diff(1, -3)
두 번째로 큰 값과 세 번째로 작은 값의 차이, diff(2, -2)
최대 값과 네 번째로 작은 값의 차이, diff(3, -1)

따라서, 위의 값 차이 중 가장 작은 값을 구하면 된다.

def minDifference(nums):
    if len(nums) <= 4:
        return 0
    nums = sorted(nums)
    candidates = [
        nums[-4] - nums[0],
        nums[-3] - nums[1],
        nums[-2] - nums[2],
        nums[-1] - nums[3],
    ]
    return min(candidates)

정렬 후 최대 4개의 인덱스를 봐야 하기 때문에, 길이가 4보다 작은 경우는 오버플로우가 발생할 수 있다. 만약 길이가 4보다 작거나 같다면, 3번의 행동 안에 모든 값을 다 같게 만들 수 있으므로 답은 0이 된다. 따라서 이 경우를 먼저 처리해줄 수 있다.
나머지는 차근차근 문제의 조건에 맞는 후보 값을 구해서 최소 값을 구한다.

여기서 좀더 파이써닉하게 풀면 다음과 같이 할 수 있다.

def minDifference(nums):
    nums = sorted(nums)
    return min(y - x for x, y in zip(nums[:4], nums[-4:]))

파이썬의 zip 연산과 슬라이싱 연산을 이용한다. nums[:4]는 nums[0]부터 nums[3]까지, nums[-4:]는 nums[-4]부터 nums[-1]까지이다. 따라서 이들을 순서대로 zip으로 묶어버리면 우리가 원하는 후보자와 정확히 일치한다. 또한 슬라이싱 연산자는 배열 크기를 넘어버리는 경우도 알아서 처리해주기 때문에 (짤림), 이 경우에는 입력 배열의 길이를 미리 쳐낼 필요가 없다. 어차피 길이가 4보다 작거나 같은 경우는 nums[:4]도 nums[-4:]도 배열 전체가 될 것이고 그러면 자연스럽게 최소 차이 값인 0을 얻을 수 있다.