목표에 가장 가까운 부분집합 합
자바스크립트 코딩테스트 문제로 meet-in-the-middle 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
정수 배열에서 몇 개의 수를 골라 만든 합 중 target에 가장 가까운 값을 구하세요.
문제 설명
정수 배열 nums와 정수 target이 주어집니다.
nums에서 원하는 원소를 골라 부분집합을 만들 수 있습니다. 아무 원소도 고르지 않는 빈 부분집합도 허용하며, 이때 합은 0입니다.
가능한 모든 부분집합 합 중 target과의 절대 차이가 가장 작은 합을 반환하는 closestSubsetSumToTarget 함수를 작성하세요.
절대 차이가 같은 후보가 여러 개라면 더 작은 합을 반환합니다.
제한사항
0 <= nums.length <= 30-1,000,000 <= nums[i] <= 1,000,000-30,000,000 <= target <= 30,000,000- 각 원소는 선택하거나 선택하지 않을 수 있습니다.
- 빈 부분집합의 합
0도 후보에 포함됩니다. - 반환값은
target에 가장 가까운 부분집합 합입니다. - 차이가 같은 후보가 여러 개이면 더 작은 합을 반환합니다.
예시
- 입력:
nums = [5, -7, 3, 5],target = 6-> 출력:6 - 입력:
nums = [2, 4, 6],target = 5-> 출력:4 - 입력:
nums = [8, -6, 4],target = 3-> 출력:2 - 입력:
nums = [10, -3, 7],target = 0-> 출력:0
힌트
- 모든 부분집합을 직접 만들면 경우의 수가
2^n이라n = 30에서 부담이 큽니다. - 배열을 절반씩 나누면 각 절반의 부분집합 합은 최대
2^15개입니다. - 한쪽 합을 고정했을 때, 반대쪽에서는
target - 고정한 합에 가장 가까운 값을 찾으면 됩니다.
해설
이 문제는 부분집합을 모두 확인해야 할 것처럼 보이지만, n이 최대 30이므로 전체 2^30가지를 직접 만들면 너무 많습니다.
대신 배열을 왼쪽 절반과 오른쪽 절반으로 나눕니다. 각 절반에서 만들 수 있는 모든 부분집합 합을 따로 구하면, 한쪽당 최대 2^15 = 32768개라 충분히 다룰 수 있습니다.
예를 들어 왼쪽 합을 leftSum이라고 하면, 오른쪽에서는 target - leftSum에 가장 가까운 값을 고르면 전체 합이 목표에 가장 가까워집니다. 오른쪽 부분집합 합 배열을 정렬해 두면 이 값 근처를 이분 탐색으로 빠르게 찾을 수 있습니다.
이분 탐색으로 찾은 위치와 바로 앞 위치를 후보로 확인하면 됩니다. 각 후보 전체 합에 대해:
Math.abs(candidate - target)이 더 작으면 정답을 갱신합니다.- 차이가 같다면
candidate가 더 작을 때 정답을 갱신합니다.
빈 부분집합도 허용되므로 각 절반의 부분집합 합 목록에는 반드시 0이 포함됩니다. nums가 빈 배열이어도 가능한 합은 0뿐이므로 자연스럽게 0을 반환할 수 있습니다.
전체 시간 복잡도는 부분집합 합 생성과 정렬, 탐색을 합쳐 O(2^(n/2) log 2^(n/2)) 수준이며, 공간 복잡도는 두 절반의 합 목록을 저장하는 O(2^(n/2))입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.