문제 정의
정렬된 정수 배열 arr이 주어졌다고 가정해 봅시다. 우리가 찾아야 하는 것은 다음 식의 값을 최소로 만드는 정수 x입니다.
abs(a[0] - x) + abs(a[1] - x) + ... + abs(a[a.length - 1] - x)
여기서 abs는 절댓값을 의미합니다. 조건을 만족하는 답이 여러 개라면, 그중 가장 작은 값을 출력해야 합니다.
예시로 이해하기
다음 배열이 주어졌을 때,
arr = [2, 4, 7]
출력 결과는 다음과 같습니다.
absoluteValuesSumMinimization(arr) = 4
abs(2 - 4) + abs(4 - 4) + abs(7 - 4) = 5이며, 어떤 숫자를 선택하더라도 이보다 작은 값은 얻을 수 없기 때문입니다.
핵심 아이디어: 중앙값(Median)
이 문제의 열쇠는 바로 중앙값입니다. 절댓값 거리의 합은 통계학의 평균 절대 오차와 같은 개념으로, 이 값을 최소화하는 지점은 항상 배열의 중앙값입니다.
- 홀수 길이 배열: 정확히 가운데 있는 요소가 답입니다.
- 짝수 길이 배열: 가운데 두 요소 사이의 모든 값이 동일한 최솟값을 가지므로, '가장 작은 값 출력' 조건에 따라 왼쪽 중앙값이 답이 됩니다.
이를 인덱스로 표현하면 arr[Math.ceil(arr.length / 2) - 1]이 됩니다.
Math.ceil(arr.length / 2)는 필요할 경우 올림을 수행합니다. 길이가 5인 배열이라면 2.5 → 3이 되어 홀수 길이 배열에서 인덱스가 하나 밀리게 됩니다.- 여기서 1을 빼면(
Math.ceil(arr.length / 2) - 1) 인덱스가 하나 내려가며, 짝수·홀수 길이 배열 모두에서 정확한 위치를 가리키게 됩니다.
구현 예제: 브루트 포스 방식
먼저 모든 후보 값에 대해 절댓값 합을 직접 계산하는, 직관적으로 이해하기 쉬운 방법부터 살펴보겠습니다.
const arr = [2, 4, 7];
const absoluteValuesSumMinimization = (arr = []) => {
const res = [];
arr.forEach(num => {
const sum = arr.reduce((accum, next) => {
return accum + Math.abs(next - num);
}, 0);
res.push(sum);
});
const lowest = Math.min(...res);
return arr[res.indexOf(lowest)];
};
console.log(absoluteValuesSumMinimization(arr));
출력 결과
콘솔에는 다음과 같이 출력됩니다.
4
이 코드는 각 요소를 후보로 삼아 전체 절댓값 합을 계산한 뒤, 최솟값을 만드는 요소를 반환합니다. 이중 반복 구조 때문에 시간 복잡도는 O(n²)입니다.
더 효율적인 풀이: O(1)
중앙값 원리를 활용하면 반복 계산 없이 단 한 줄로 해결할 수 있습니다.
const absoluteValuesSumMinimization = arr => arr[Math.ceil(arr.length / 2) - 1]; console.log(absoluteValuesSumMinimization([2, 4, 7])); // 4 console.log(absoluteValuesSumMinimization([1, 2, 3, 4])); // 2
배열이 이미 정렬되어 있다는 전제만 있으면, 별도의 연산 없이 중앙값 인덱스의 요소를 곧바로 반환하면 됩니다. 시간 복잡도가 O(1)이므로 아주 큰 배열에서도 즉시 답을 구할 수 있습니다.
마무리
절댓값 거리의 합을 최소화하는 값은 항상 중앙값이라는 사실만 기억하면 이 문제는 한 줄의 코드로 해결됩니다. 브루트 포스 풀이는 원리를 이해하는 데 유용하지만, 실전에서는 중앙값 공식을 사용하는 것이 가장 효율적입니다.