파이썬으로 풀어보는 최소 범위 I 문제: 배열 요소 조정으로 최대·최솟값 차이 줄이기

정수로 이루어진 배열 A가 주어졌을 때, 각 원소 A[i]에 대해 [-K, K] 범위 내의 임의의 값 x를 선택하여 더할 수 있다고 가정해 봅시다. 이 과정을 모든 원소에 적용하면 새로운 배열 B가 만들어집니다. 이때 우리가 구해야 할 것은 배열 B의 최댓값과 최솟값 사이의 차이를 최소화하는 것입니다.

예를 들어, 입력이 A = [0, 10], K = 2라고 해 보겠습니다. 이 경우 B = [2, 8]이 될 수 있으므로, 정답은 8 - 2 = 6입니다.

문제 해결 접근 방식

이 문제는 직관적인 관찰 하나만으로 간단히 해결할 수 있습니다. 배열에서 최댓값과 최솟값에만 집중하면 됩니다.

• 최댓값에는 최대 K만큼 작게 만들 수 있으므로, 조정 후의 최댓값은 (max(A) - K)입니다.
• 최솟값에는 최대 K만큼 크게 만들 수 있으므로, 조정 후의 최솟값은 (min(A) + K)입니다.
• 두 값의 차이가 음수라면, 즉 두 값이 교차한다면 최댓값과 최솟값을 같게 만드는 것이 가능하므로 정답은 0입니다.

알고리즘 단계

1. MAX := (배열 A의 최댓값) - K
2. MIN := (배열 A의 최솟값) + K
3. difference := MAX - MIN 계산
4. difference가 0보다 작으면 0을 반환하고, 그렇지 않으면 difference를 반환합니다.

구현 예제

class Solution:
    def smallestRangeI(self, A, K):
        MAX = max(A) - K
        MIN = min(A) + K
        difference = MAX - MIN
        if difference < 0:
            return 0
        else:
            return difference

ob = Solution()
print(ob.smallestRangeI([0, 10], 2))

입력

[0, 10], 2

출력

6

복잡도 분석

이 알고리즘은 배열을 한 번씩 순회하여 최댓값과 최솟값을 구하므로 시간 복잡도는 O(n)이며, 추가적인 공간을 거의 사용하지 않아 공간 복잡도는 O(1)입니다. 배열 전체를 탐색하지 않고 양 끝값만 고려하기 때문에 매우 효율적인 해법이라 할 수 있습니다.