문제 이해하기
타워들의 높이가 담긴 리스트와 양의 정수 k가 주어집니다. 우리는 k개의 타워를 선택한 뒤, 벽돌을 추가하여 선택한 타워들의 높이를 모두 동일하게 만들어야 하며, 이때 사용하는 벽돌의 개수를 최소화하는 것이 목표입니다. 즉, k개의 타워를 골라 같은 높이로 만들 때 필요한 최소 벽돌 수를 구하는 프로그램을 작성해야 합니다.
예를 들어, 입력이 heights = [5, 8, 32, 15, 41]이고 k = 3이라면 출력은 17이 됩니다. 높이가 5, 8, 15인 세 개의 타워를 선택하면, 모두 높이 15로 맞추는 데 (15−5) + (15−8) + (15−15) = 17개의 벽돌이 필요하기 때문입니다.
접근 방법: 정렬 + 슬라이딩 윈도우
이 문제는 정렬과 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 타워를 높이순으로 정렬하면, 최적의 k개 타워는 반드시 정렬된 리스트에서 연속된 구간에 존재합니다. 따라서 길이가 k인 모든 연속 구간에 대해, 해당 구간의 마지막 원소(최댓값)를 목표 높이로 삼았을 때 필요한 벽돌 수를 계산하고, 그중 최솟값을 찾으면 됩니다.
알고리즘 단계
- heights 리스트를 오름차순으로 정렬합니다.
- ans := 무한대(infinity), s := 0으로 초기화합니다.
- 각 인덱스 i와 값 x에 대해 다음을 반복합니다.
- s := s + x (현재 값을 누적합에 더함)
- i >= k이면 s := s − heights[i − k] (윈도우에서 벗어난 값 제거)
- i >= k − 1이면 ans := min(ans, x × k − s) (현재 윈도우에서 필요한 벽돌 수 계산 후 최솟값 갱신)
- ans를 반환합니다.
여기서 x * k - s의 의미는 다음과 같습니다. 현재 윈도우의 마지막 값 x가 목표 높이이며, k개의 타워를 모두 높이 x로 만드는 데 필요한 총 벽돌 수는 목표 높이의 총합(x × k)에서 현재 윈도우의 실제 높이 합(s)을 뺀 값입니다.
구현 예제
class Solution:
def solve(self, heights, k):
heights.sort()
ans = float("inf")
s = 0
for i, x in enumerate(heights):
s += x
if i >= k:
s -= heights[i - k]
if i >= k - 1:
ans = min(ans, x * k - s)
return ans
ob = Solution()
heights = [5, 8, 32, 15, 41]
k = 3
print(ob.solve(heights, k))입력
[5, 8, 32, 15, 41], 3
출력
17
복잡도 분석
정렬에 O(n log n), 슬라이딩 윈도우 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 추가 배열 없이 누적합 변수만 사용하므로 공간 복잡도는 O(1)입니다. 완전 탐색으로 모든 조합을 확인하는 O(nk) 방식보다 훨씬 효율적입니다.