합이 K의 배수가 되게 만드는 최대 짝 수
자바스크립트 코딩테스트 문제로 remainder-grouping 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
한 번 쓴 숫자는 다시 사용할 수 없을 때, 두 수의 합이 k의 배수가 되도록 만들 수 있는 최대 짝의 개수를 구하세요.
문제 설명
정수 배열 nums와 양의 정수 k가 주어집니다.
서로 다른 두 원소를 짝으로 묶을 때, 각 짝의 합이 k의 배수이면 유효한 짝입니다.
각 원소는 최대 한 번만 사용할 수 있습니다.
만들 수 있는 유효한 짝의 최대 개수를 반환하는 maxDivisiblePairsByK 함수를 작성하세요.
제한사항
1 <= nums.length <= 100,0001 <= nums[i] <= 1,000,000,0001 <= k <= 100,000- 각 원소는 최대 한 번만 사용할 수 있습니다.
- 반환값은 만들 수 있는 유효한 짝의 최대 개수입니다.
예시
- 입력:
nums = [1, 2, 3, 4, 5, 10, 6, 7, 8, 9],k = 5→ 출력:5 - 입력:
nums = [2, 2, 1, 7, 5, 3],k = 4→ 출력:3 - 입력:
nums = [5, 5, 5],k = 5→ 출력:1 - 입력:
nums = [1, 1, 1, 1],k = 3→ 출력:0
힌트
- 실제 값보다
k로 나눈 나머지가 더 중요합니다. - 어떤 수의 나머지가
r라면, 짝이 되려면 다른 수의 나머지는 무엇이어야 할까요? - 나머지
0은 조금 특별하고,k가 짝수일 때k / 2도 특별합니다.
해설
핵심은 각 숫자 자체를 직접 짝짓는 대신, 나머지끼리 어떤 조합이 가능한지 보는 것입니다.
어떤 두 수의 합이 k의 배수가 되려면,
두 수를 k로 나눈 나머지의 합이 k가 되거나 0이 되어야 합니다.
예를 들어 k = 5라면:
- 나머지
1은 나머지4와 짝이 되어야 하고 - 나머지
2는 나머지3과 짝이 되어야 하며 - 나머지
0은 나머지0끼리만 짝이 됩니다.
풀이 순서
- 모든 숫자를
k로 나눈 나머지 개수를 셉니다. - 나머지
0그룹에서는count[0] / 2개만 짝을 만들 수 있습니다. 1부터Math.floor((k - 1) / 2)까지 보면서, 나머지r와k - r는min(count[r], count[k-r])개만 짝이 됩니다.k가 짝수라면 나머지k / 2그룹도 자기들끼리만 짝을 만들 수 있으므로count[k / 2] / 2를 더합니다.- 모두 합치면 최대 짝 수가 됩니다.
왜 이게 최대일까?
나머지 r인 수는 결국 나머지 k-r인 수와만 유효한 짝을 만들 수 있습니다.
즉 이 그룹은 서로의 재고만큼만 짝을 만들 수 있으므로 최댓값은 항상 min(count[r], count[k-r])입니다.
그보다 더 많이 만드는 방법은 없습니다.
0과 k / 2는 자기 그룹 안에서만 짝이 되기 때문에 두 개씩 묶는 것 외에는 방법이 없습니다.
그래서 각각 절반만 짝 수로 기여합니다.
예시로 보기
nums = [2, 2, 1, 7, 5, 3], k = 4
나머지는 각각:
2, 2, 1, 3, 1, 3
개수를 세면:
count[0] = 0count[1] = 2count[2] = 2count[3] = 2
가능한 짝 수는:
- 나머지
1과3→min(2, 2) = 2 - 나머지
2와2→2 / 2 = 1
총 3쌍입니다.
이 방법은 배열을 한 번 돌며 개수를 세고, 나머지 그룹을 한 번 더 확인하면 되므로 시간 복잡도는 O(n + k)이고 추가 공간은 O(k)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.