문제 이해하기
배열 A와 정수 k가 주어졌을 때, A의 원소들을 선택하여 크기가 k인 배열 arr를 만들고 불공정성(unfairness)을 최소화하는 프로그램을 작성해 보겠습니다. 여기서 불공정성은 다음 공식으로 계산합니다.
(arr의 최댓값) − (arr의 최솟값)
예를 들어 입력이 A = [25, 120, 350, 150, 2500, 25, 35]이고 k = 3이라면 출력은 10이 됩니다. [25, 25, 35]를 선택하면 max(arr) = 35, min(arr) = 25이므로 두 값의 차이가 10으로 가장 작기 때문입니다.
해결 접근 방법
이 문제는 정렬과 슬라이딩 윈도우 기법으로 효율적으로 해결할 수 있습니다. 배열을 오름차순으로 정렬하면, 최댓값과 최솟값의 차이가 가장 작은 k개의 원소는 반드시 정렬된 배열에서 연속된 구간에 존재하게 됩니다. 따라서 크기 k의 모든 연속 구간(윈도우)을 확인하면서, 각 구간의 마지막 원소와 첫 번째 원소의 차이 중 가장 작은 값을 찾으면 됩니다.
단계별 절차는 다음과 같습니다.
- i := 0으로 초기화합니다.
- 리스트 A를 오름차순으로 정렬합니다.
- n := A의 크기로 설정합니다.
- m := A[n-1]로 초기화합니다. (차이 값의 초기 상한선)
- i < n-k인 동안 반복합니다.
- 만약 A[i+k-1] - A[i] < m이면, m := A[i+k-1] - A[i]로 갱신합니다.
- i를 1씩 증가시킵니다.
- 반복이 끝나면 m을 반환합니다.
예제 코드
다음 파이썬 구현을 통해 더 잘 이해해 보겠습니다.
def solve(A, k):
i = 0
A.sort()
n = len(A)
m = A[n-1]
x = 0
y = 0
while i < n-k:
if(A[i+k-1]-A[i] < m):
m = A[i+k-1]-A[i]
i += 1
return m
A = [25, 120, 350, 150, 2500, 25, 35]
k = 3
print(solve(A, k))입력
[25, 120, 350, 150, 2500, 25, 35]
출력
10
복잡도 분석
정렬에 O(n log n)의 시간이 소요되고, 슬라이딩 윈도우 탐색에는 O(n)의 시간이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 정렬된 배열에서 연속된 구간만 확인하면 되기 때문에 모든 조합을 탐색하는 완전 탐색 방식(O(n^k))보다 훨씬 효율적입니다.