파일 묶음 합치기 최소 비용

자바스크립트 코딩테스트 문제로 heap 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium heap 함수명: solution 제한 시간: 300ms

정수 배열 files가 주어질 때, 파일 묶음을 하나로 합칠 때 드는 최소 총 비용을 반환하는 solution 함수를 작성하세요.

두 묶음을 한 번 합칠 때 드는 비용은 두 묶음 크기의 합이며, 합쳐진 묶음은 다시 다음 합치기에 사용할 수 있습니다.

제한사항

• 1 <= files.length <= 100000
• 1 <= files[i] <= 1000000
• 반환값은 모든 파일을 하나로 합칠 때 필요한 최소 총 비용입니다.
• 파일이 1개뿐이면 이미 하나의 묶음이므로 비용은 0입니다.

예시

• 입력: [40, 30, 30, 50] → 출력: 300
• 입력: [10] → 출력: 0
• 입력: [1, 2, 3, 4, 5] → 출력: 33

힌트

• 가장 큰 파일부터 합친다고 항상 유리하지는 않습니다.
• 매번 가장 작은 두 묶음을 먼저 꺼낼 수 있으면 좋습니다.
• 이런 작업은 우선순위 큐(최소 힙)가 잘 맞습니다.

해설

이 문제의 핵심은 항상 가장 작은 두 묶음을 먼저 합쳐야 총 비용이 최소가 된다는 점입니다.

예를 들어 40, 30, 30, 50이 있을 때:

1. 30과 30을 먼저 합치면 비용 60
2. 남은 묶음은 40, 50, 60
3. 40과 50을 합치면 비용 90
4. 남은 묶음은 60, 90
5. 마지막으로 합치면 비용 150
6. 총 비용은 60 + 90 + 150 = 300입니다.

반대로 큰 묶음을 먼저 합치면 초반에 만들어진 큰 합이 이후 합치기에도 계속 더해져서 총 비용이 커질 수 있습니다.

풀이 흐름은 다음과 같습니다.

1. 모든 파일 크기를 최소 힙에 넣습니다.
2. 힙의 원소가 2개 이상인 동안 가장 작은 두 값을 꺼냅니다.
3. 두 값을 더한 비용을 정답에 누적합니다.
4. 새로 만들어진 묶음 크기를 다시 힙에 넣습니다.
5. 힙에 하나만 남으면 누적 비용을 반환합니다.

이 방식은 매 단계에서 최선의 선택을 반복하는 그리디 + 최소 힙 풀이입니다. 알고리즘 문제에서 우선순위 큐가 어디에 쓰이는지 익히기 좋은 대표 유형입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

입력값 []

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.