N개의 정수로 이루어진 배열 arr[]와 정수 K가 주어졌을 때, 두 원소의 합 arr[i] + arr[j]가 K로 나누어 떨어지는 쌍의 최대 개수를 구하는 것이 이번 문제의 목표입니다.
단, 한 번 쌍에 사용된 인덱스는 다른 쌍에서 다시 사용할 수 없다는 조건이 있습니다.
입력 및 출력 예시
예시 1
입력
arr[] = {1, 2, 5, 8, 3}, K = 2출력
2
설명 — 조건을 만족하는 쌍은 (0, 2)와 (1, 3)입니다. 즉, 1+5=6과 2+8=10이며, 두 값 모두 2로 나누어 떨어집니다.
(0, 4), (1, 3) 또는 (2, 4), (1, 3)과 같은 다른 조합도 가능하지만, 결과는 동일하게 2입니다.
예시 2
입력
arr[] = {1, 3, 5, 2, 3, 4}, K = 3출력
3
해결 접근 방법
- int형 변수 n에 배열의 크기를 저장합니다.
- MaxPairs() 함수에서는 unordered_map을 활용하여 배열의 각 원소마다 um[arr[i] % K] 값을 1씩 증가시킵니다. 즉, 각 원소를 K로 나눈 나머지별로 개수를 그룹화합니다.
- 맵을 순회하면서 가능한 모든 나머지 값(um 값)을 확인합니다.
- 나머지가 0인 원소들은 서로 더했을 때 K로 나누어 떨어지므로, 쌍의 개수는 um[0] / 2가 됩니다.
- 나머지가 'a'인 원소와 'K-a'인 원소를 더하면 K의 배수가 되므로, min(um[a], um[K-a])만큼 쌍을 만들 수 있습니다.
- 쌍을 만든 후에는 사용된 원소의 개수를 um 값에서 차감하여 같은 인덱스가 중복 사용되지 않도록 합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int MaxPairs(int arr[], int size, int K){
unordered_map<int, int> um;
for (int i = 0; i < size; i++){
um[arr[i] % K]++;
}
int count = 0;
/*해시 값보다 작은 모든 수에 대해 반복*/
for (auto it : um){
// 나머지가 0인 경우
if (it.first == 0){
//같은 그룹끼리 짝을 이루므로 절반만큼 쌍 생성
count += it.second / 2;
if (it.first % 2 == 0){
um[it.first] = 0;
}
else{
um[it.first] = 1;
}
}
else{
int first = it.first;
int second = K - it.first;
//더 적게 등장한 쪽 확인
if (um[first] < um[second]){
//최솟값만큼 쌍 생성
count += um[first];
//사용된 쌍 차감
um[second] -= um[first];
um[first] = 0;
}
else if (um[first] > um[second]){
//최솟값만큼 쌍 생성
count += um[second];
//사용된 쌍 차감
um[first] -= um[second];
um[second] = 0;
}
else{
//두 수가 같은지 확인
if (first == second){
//같다면 쌍의 개수는 절반
count += it.second / 2;
//남은 개수 확인
if (it.first % 2 == 0)
um[it.first] = 0;
else
um[it.first] = 1;
}
else{
//쌍의 개수 저장
count += um[first];
um[first] = 0;
um[second] = 0;
}
}
}
}
return count;
}
//메인 함수
int main(){
int arr[] = { 3, 6, 7, 9, 4, 4, 10 };
int size = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout<<"Maximize the number of sum pairs which are divisible by K is: "<<MaxPairs(arr, size, K);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
Maximize the number of sum pairs which are divisible by K is: 3
복잡도 분석
시간 복잡도: O(N + K) — 배열을 한 번 순회하며 나머지별 빈도를 계산한 후(O(N)), 해시 맵을 순회하면서 쌍의 개수를 산출합니다.
공간 복잡도: O(min(N, K)) — 나머지 값별 빈도를 저장하기 위한 해시 맵이 필요합니다.