정수 배열 A가 주어졌을 때, 각 원소 A[i]마다 x = -K 또는 x = K 중 하나를 선택하여 딱 한 번 더하는 문제를 생각해 봅시다. 이 과정을 거치면 새로운 배열 B가 만들어지는데, 우리가 구해야 하는 것은 B의 최댓값과 최솟값 사이 차이가 가장 작아지도록 만드는 것입니다.
예를 들어 입력이 A = [0, 10], K = 2라고 해 보겠습니다. 각 원소에 ±2를 더한 결과 B = [2, 8]을 얻을 수 있으며, 이때 최댓값과 최솟값의 차이는 8 - 2 = 6입니다. 따라서 정답은 6이 됩니다.
문제 해결 접근 방법
이 문제는 정렬과 그리디(Greedy) 기법을 활용하면 효율적으로 해결할 수 있습니다. 배열을 정렬한 뒤, 특정 지점을 기준으로 앞쪽 원소에는 +K를, 뒤쪽 원소에는 -K를 적용하는 분할 지점(split point)을 모두 시도해 보는 것이 핵심 아이디어입니다. 구체적인 단계는 다음과 같습니다.
ret := 0, n := 배열 A의 크기로 초기화합니다.
배열 A를 오름차순으로 정렬합니다.
ret := A의 마지막 원소 − 첫 번째 원소로 설정합니다. (어떤 연산도 하지 않았을 때의 차이)
right := 마지막 원소 − K, left := 첫 번째 원소 + K로 설정합니다.
i를 0부터 n − 2까지 반복하며 다음을 수행합니다.
mx := max(A[i] + k, right)
mn := min(A[i + 1] − k, left)
ret := min(ret, mx − mn)
ret을 반환합니다.
여기서 mx는 분할 지점 이후의 새로운 최댓값 후보, mn은 새로운 최솟값 후보를 의미합니다. 모든 분할 지점을 검사하면서 최댓값과 최솟값의 차이가 최소가 되는 경우를 찾으면 됩니다.
다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int smallestRangeII(vector<int>& A, int k) {
int ret = 0;
int n = A.size();
sort(A.begin(), A.end());
ret = A[n - 1] - A[0];
int mx, mn;
int right = A[n - 1] - k;
int left = A[0] + k;
for(int i = 0; i < n - 1; i++){
mx = max(A[i] + k, right);
mn = min(A[i + 1] - k, left);
ret = min(ret, mx - mn);
}
return ret;
}
};
main(){
vector<int> v = {0, 10};
Solution ob;
cout << (ob.smallestRangeII(v, 2));
}입력
[0,10] 2
출력
6