[LeetCode] 910. Smallest Range II

출처: https://leetcode.com/problems/smallest-range-ii/

문제

정수 배열 A에서, 모든 A[i]에 -K 또는 K를 선택하여 더한다(오직 한번).

이 과정 후의 배열을 B라 하자.

배열 B의 원소 중 가장 큰 값과 작은 값의 차이가 가장 작을 때의 차를 반환하라.

예제

Input: A[0,10], K = 2
Ouput: 6
Explanation: B = [2,8]

Input: A = [1,3,6], K = 3
Output: 3
Explanation: B = [4,6,3]

풀이

우선, 배열의 최솟값, 최댓값을 쉽게 파악하기 위해서 입력으로 주어지는 배열 A를 오름차순으로 정렬한다.

 

이 상태에서 배열의 최댓값 - 최솟값의 크기를 줄이기 위해서 최댓값 - K, 최솟값 + K를 수행하면 끝일 것 같지만, 관건은 그 사이의 값들(인덱스 1 ~ n-2, n = A배열의 크기) 또한 -K 혹은 +K를 통해 값이 변한다는 것이다. 즉, 배열 내부에서 최댓값과 최솟값의 위치가 변할 수 있다는 것이다.

 

이러한 문제를 인식하고 본격적인 풀이에 들어가면

각 지점이 가장 큰 값이 될 수 있는 상황을 만들고, 그 상황에서 만들 수 있는 최댓값 - 최솟값을 계산하는 식으로 문제를 해결할 수 있다.

 

임의의 지점 i가 최대가 될 수 있으려면 A[i] + K가 되어야 한다. 그리고 i보다 큰 인덱스의 값들은 -K가 되어야 할 것이다. 쉽게 생각해서 현재 A가 오름차순으로 정렬되어 있기 때문에 i < j라면 A[i] < A[j]이다. 여기서 양쪽에 모두 +K를 해버리면 A[i]+K < A[j]+K로 유지가 되기 때문에 i는 절대 배열 내에서 최댓값이 될 수가 없다. 이 때문에 -K를 해주는 것이다.

 

i보다 작은 인덱스는 어떠할까. i보다 작은 인덱스는 +K를 해줘야한다. 왜냐하면 i보다 작은 인덱스에 -K를 해버리면 i인덱스와의 격차가 원래보다 커지게 되는데, 이는 가장 작은 최댓값 - 최솟값을 찾는 현재 문제에 적합하지 않은 변화이다.

 

현재까지 내용을 정리해서 그림으로 표현하면 다음의 그림이 된다.

여기서 한가지 생각할 점은 이 상황에서 "i지점이 진짜 배열 내에서 최댓값인가?" 라는 점이다. i가 최대가 될 수 있도록 상황을 만들긴 했지만, 실제로 가장 큰 값은 다른 값이 될 수도 있다. 예를 들어 다음과 같은 상황을 살펴보자.

A[i] = 2, A[i+1] = 10, K = 1

B[i] = A[i] + K = 3
B[i+1] = A[i+1] - K = 9

B[i] < B[i+1]

이와같은 상황이 존재하기 때문에 진짜 최댓값을 찾기 위해서 max(A[i]+k, A[n-1]-K)를 수행한다. i보다 작은 지점은 위 그림에서 파악할 수 있듯이 볼 필요가 없으며, i보다 큰 부분에서는 마지막 인덱스 부분만 체크하면 된다. 이것이 바로 처음에 정렬을 했기 때문에 얻을 수 있는 결과이다.

 

최솟값 또한 최댓값과 비슷한 원리로 min(A[0]+K, A[i+1]-K)을 통해서 구할 수 이다. 이제 최댓값과 최솟값을 찾았기 때문에 그 차이를 손쉽게 계산할 수 있게 되었다.

 

남은 작업은 i를 0부터 n-2까지 돌면서 계산되어지는 최댓값 - 최솟값을 관찰하면서 가장 작은 값을 구하는 일이다.

// JavaScript

var smallestRangeII = function(A, K) {
    if (A.length == 1) return 0;

    A = A.sort((a, b) => a - b);
    let answer = A[A.length-1] - A[0];
    for (let i = 0; i < A.length-1; i++) {
        const max = Math.max(A[A.length-1] - K, A[i] + K);
        const min = Math.min(A[0] + K, A[i+1] - K);
        answer = Math.min(answer, max - min);
    }

    return answer;
};

Github: 910.js