숫자로 이루어진 리스트 nums가 있다고 가정해 보겠습니다. 우리는 리스트의 한 요소를 임의의 값으로 바꿀 수 있는 연산을 사용할 수 있으며, 이 연산은 최대 3번까지만 수행할 수 있습니다. 이때 연산을 마친 뒤 리스트에서 최댓값과 최솟값의 차이가 가능한 한 작아지도록 만드는 것이 목표입니다.
예를 들어 입력이 nums = [2, 3, 4, 5, 6, 7]이라면 출력은 2입니다. 리스트를 [4, 3, 4, 5, 4, 4]로 바꾸면 최댓값 5에서 최솟값 3을 뺀 5 − 3 = 2가 되기 때문입니다.
문제 해결 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- nums의 길이가 4 이하라면 모든 요소를 같은 값으로 맞출 수 있으므로 0을 반환합니다.
- n := nums의 길이로 설정합니다.
- 리스트 nums를 오름차순으로 정렬합니다.
- i가 0부터 3까지일 때 각각 nums[n-4+i] − nums[i]를 계산하고, 그중 최소값을 반환합니다.
왜 이 방법이 동작할까?
최대 3개의 요소를 자유롭게 바꿀 수 있다는 것은, 사실상 정렬된 배열의 양 끝에서 최대 3개의 값을 "버리는" 것과 같습니다. 즉, 남길 구간의 시작점을 왼쪽에서 몇 개 건너뛸지(i), 끝점을 오른쪽에서 몇 개 건너뛸지(3−i)를 정하는 문제로 볼 수 있습니다. 가능한 조합은 다음 네 가지뿐입니다.
- 가장 큰 값 3개를 변경하는 경우: nums[n-4] − nums[0]
- 가장 큰 값 2개와 가장 작은 값 1개를 변경하는 경우: nums[n-3] − nums[1]
- 가장 큰 값 1개와 가장 작은 값 2개를 변경하는 경우: nums[n-2] − nums[2]
- 가장 작은 값 3개를 변경하는 경우: nums[n-1] − nums[3]
이 네 가지 경우 중 가장 작은 차이가 곧 정답이 됩니다.
구현 예시
class Solution:
def solve(self, nums):
if len(nums) <= 4:
return 0
nums.sort()
return min(nums[-4 + i] - nums[i] for i in range(4))
ob = Solution()
nums = [2, 3, 4, 5, 6, 7]
print(ob.solve(nums))실행 결과
입력:
[2, 3, 4, 5, 6, 7]출력:
2이 풀이의 시간 복잡도는 정렬 과정에 의해 지배되므로 O(n log n)이며, 제자리 정렬을 사용하는 경우 공간 복잡도는 O(1)입니다.