문제 개요
숫자로 이루어진 리스트 nums와 정수 k가 주어졌다고 가정해 봅시다. 이때 nums에서 요소들을 선택하여 크기가 k인 리스트를 만들어야 하며, 그 리스트 안에서 가장 큰 값과 가장 작은 값의 차이가 최소가 되도록 해야 합니다. 최종적으로 우리는 이 차이를 반환하면 됩니다.
예시
입력이 다음과 같다고 해보겠습니다.
- nums = [3, 11, 6, 2, 9]
- k = 3
이 경우 최적의 리스트는 [2, 3, 6]이며, 가장 큰 값 6과 가장 작은 값 2의 차이는 4입니다. 따라서 출력 결과는 4가 됩니다.
해결 접근 방법
이 문제는 정렬을 활용하면 효율적으로 풀 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- 먼저 리스트 nums를 오름차순으로 정렬합니다.
- 결과를 저장할 새로운 리스트 ls를 생성합니다.
- i를 0부터 (nums의 길이 - k)까지 반복하면서, 각 구간에서 nums[i + k - 1] - nums[i] 값을 계산하여 ls에 추가합니다.
- 모든 반복이 끝나면 ls 중 최솟값을 반환합니다.
정렬된 상태에서는 서로 인접한 k개의 요소들이 최소 차이를 만드는 후보가 되므로, 연속된 k개 요소의 양끝 값 차이만 비교하면 됩니다. 이 방법의 시간 복잡도는 정렬에 의해 지배되며 O(n log n)입니다.
구현 예제
class Solution:
def solve(self, nums, k):
nums.sort()
ls = []
for i in range(len(nums) - k + 1):
ls.append(nums[i + k - 1] - nums[i])
return min(ls)
ob = Solution()
nums = [3, 11, 6, 2, 9]
k = 3
print(ob.solve(nums, k))
입력
[3, 11, 6, 2, 9], 3
출력
4
코드 설명
위 코드에서 solve() 메서드는 먼저 입력 리스트를 정렬합니다. 그런 다음 길이가 k인 모든 연속 구간(슬라이딩 윈도우)에 대해 마지막 요소와 첫 번째 요소의 차이를 계산하여 ls에 저장합니다. 정렬된 리스트에서 각 구간의 최댓값은 구간의 마지막 요소, 최솟값은 첫 번째 요소이기 때문입니다. 마지막으로 min() 함수를 사용해 계산된 차이들 중 가장 작은 값을 반환함으로써 문제의 답을 얻습니다.