1509. Minimum Difference Between Largest and Smallest Value in Three Moves

문제 링크: https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/

 

Integer array가 주어지고, 최대 3개의 숫자를 바꿀 수 있을 때, 수행 후 array 내 최댓값과 최솟값의 차이의 최솟값을 구하는 문제이다.

 

len(array)가 최대 100000이기 때문에 모든 수를 일일이 비교해서 뭔가를 할 수는 없고... 그래서 정말 필요한 숫자끼리만 비교를 하면 된다. 정렬 후, 가장 큰 수 4개, 가장 작은 수 4개만 비교하면 된다.

 

분기를 2개로 나누면,

  - 숫자가 4개 이하라면, 한 값으로 모두 바꿀 수 있기 때문에 최솟값은 0이다

  - 아니라면 가장 큰 수 4개 - 가장 작은 수 4개 간 차이를 순서대로 구한 값 중 가장 작은 값이 답이 된다.

    - 정렬된 array [a, b, c, d, e, f, g, h]가 있을 때, min([e-a, f-b, g-c, h-e, h-a])

    - 이렇게만 해도 되는 이유는, optimal한 케이스가 있을 때 그 밖 바운더리에 있는 숫자 3개를 안쪽으로 바꿀 수 있기 때문이다.

    - 최솟값을 구할 때 initialize는 array 내 최댓값 - 최솟값으로 잡아두면 된다.