두 드론 팀의 적재 차이 최소화
자바스크립트 코딩테스트 문제로 meet-in-the-middle 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
한 번에 한 팀씩 출발하는 두 드론 팀이 있습니다. 각 짐의 무게가 담긴 배열 weights가 주어질 때, 모든 짐을 정확히 한 팀에만 배정해 두 팀의 총 적재량 차이를 최소로 만드세요.
반환값은 가능한 최소 절대 차이입니다.
제한사항
1 <= weights.length <= 301 <= weights[i] <= 1,000,000,000- 모든 짐은 정확히 한 번만 사용해야 합니다.
- 한 팀이 짐을 하나도 맡지 않아도 됩니다.
- 반환값은 두 팀 총 적재량 차이의 최솟값입니다.
예시
- 입력:
weights = [8, 6, 5, 4]→ 출력:18 + 4 = 12,6 + 5 = 11로 나누면 차이는1입니다.
- 입력:
weights = [1, 2, 3, 9]→ 출력:3- 한 팀을
1 + 2 + 3 = 6, 다른 팀을9로 두면 차이는3입니다.
- 한 팀을
- 입력:
weights = [7]→ 출력:7- 한 팀이
7, 다른 팀이0을 맡는 경우만 가능합니다.
- 한 팀이
힌트
- 전체 짐을 두 팀으로 나누는 것은 결국 어떤 짐들을 첫 번째 팀에 넣을지 고르는 문제입니다.
- 첫 번째 팀의 합이 전체 합의 절반에 가까울수록 두 팀 차이는 작아집니다.
n = 30이면 전체 부분집합2^30개를 전부 보기는 부담스럽지만, 배열을 절반으로 나누면 상황이 달라집니다.
해설
첫 번째 팀의 적재량을 picked라고 하면, 두 번째 팀의 적재량은 total - picked입니다.
우리가 최소화하려는 값은 다음과 같습니다.
|picked - (total - picked)| = |total - 2 * picked|
즉, picked를 전체 합의 절반에 최대한 가깝게 만들면 됩니다.
문제는 가능한 picked 값이 부분집합 합이라 경우의 수가 많다는 점입니다. weights.length가 최대 30이므로 전체 완전탐색은 2^30이라 브라우저 환경에서 부담스럽습니다.
여기서 meet-in-the-middle을 사용합니다.
- 배열을 왼쪽 절반과 오른쪽 절반으로 나눕니다.
- 각 절반에서 만들 수 있는 모든 부분합을 구합니다.
- 오른쪽 부분합 배열을 정렬합니다.
- 왼쪽 부분합
leftSum하나를 고를 때마다,target = total / 2 - leftSum에 가장 가까운 오른쪽 부분합을 이분 탐색으로 찾습니다. - 그 조합으로 만든 전체
picked = leftSum + rightSum에 대해|total - 2 * picked|를 계산하고 최솟값을 갱신합니다.
왜 양옆 후보를 같이 봐야 할까요?
이분 탐색으로 찾은 위치는 target 이상이 처음 나오는 자리입니다. 하지만 실제 최적값은 그 바로 앞 값일 수도 있으므로, idx와 idx - 1 둘 다 검사해야 안전합니다.
예를 들어 weights = [8, 6, 5, 4]라면 전체 합은 23, 목표 절반은 11.5입니다.
- 왼쪽 절반
[8, 6]의 부분합:0, 8, 6, 14 - 오른쪽 절반
[5, 4]의 부분합:0, 5, 4, 9
예를 들어 leftSum = 8이면 오른쪽에서 3.5에 가장 가까운 합을 찾고, 4를 고르면 전체 picked = 12가 됩니다. 이때 차이는 |23 - 24| = 1입니다.
각 절반 크기는 최대 15이므로 부분합 개수는 최대 2^15 = 32768개입니다. 따라서 전체 시간 복잡도는 부분합 생성과 정렬, 이분 탐색을 합쳐 대략 O(2^(n/2) log 2^(n/2))이고, 추가 공간 복잡도는 O(2^(n/2))입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.