문제 개요
N개의 양의 정수로 이루어진 배열과 변수 K가 주어져 있다고 가정해 보겠습니다. 이때 임의의 두 원소의 차이가 k로 나누어떨어지는 정확히 m개의 원소로 구성된 집합을 찾아야 합니다.
예를 들어 배열이 A = [4, 7, 10, 6, 9]이고 k = 3, m = 3이라면 출력은 "yes"입니다. 4, 7, 10처럼 서로 간의 차이(3, 3, 6)가 모두 3으로 나누어떨어지는 세 원소를 찾을 수 있기 때문입니다.
접근 방법: 나머지(Remainder) 활용
이 문제를 효율적으로 해결하려면 각 원소를 k로 나눈 나머지를 추적해야 합니다. 핵심 아이디어는 다음과 같습니다.
- k로 나눈 나머지가 서로 같은 두 수의 차이는 반드시 k로 나누어떨어집니다.
- 크기가 k인 2차원 배열 rem[][]을 만들고, 인덱스는 나머지 값을 나타내며, 각 인덱스에는 해당 나머지를 가지는 원소들을 저장합니다.
- 나머지 그룹들을 순회하면서 크기가 m 이상인 그룹이 존재하는지 확인합니다. 존재한다면 해당 그룹에서 m개의 원소를 선택하면 되고, 그렇지 않다면 조건을 만족하는 집합을 만들 수 없습니다.
C++ 구현 예제
#include<iostream>
#include<vector>
using namespace std;
void searchElementsSet(int arr[], int n, int k, int m) {
vector<int> rem_matrix[k];
for (int i = 0; i < n; i++) {
int rem = arr[i] % k;
rem_matrix[rem].push_back(arr[i]);
}
for (int i = 0; i < k; i++) {
if (rem_matrix[i].size() >= m) {
cout << "Yes Possible"<<endl;
for (int j = 0; j < m; j++)
cout << rem_matrix[i][j] << " ";
return;
}
}
cout << "Impossible";
}
int main() {
int arr[] = {4, 7, 10, 6, 9};
int k = 3;
int m = 3;
int n = sizeof(arr) / sizeof(arr[0]);
searchElementsSet(arr, n, k, m);
}실행 결과
Yes Possible 4 7 10
동작 원리와 복잡도 분석
위 코드는 먼저 모든 원소를 한 번씩 순회하면서 k로 나눈 나머지에 따라 버킷(bucket)에 분류합니다. 이후 각 버킷의 크기를 검사하여 m개 이상의 원소를 담고 있는 첫 번째 그룹을 찾으면, 그중 m개를 출력하고 종료합니다.
시간 복잡도는 원소 분류에 O(n), 그룹 검사에 O(k)가 소요되므로 전체적으로 O(n + k)이며, 공간 복잡도는 나머지 버킷을 저장하기 위해 O(n)입니다. 완전 탐색으로 모든 조합을 확인하는 O(n^m) 방식보다 훨씬 효율적이라는 점이 이 접근법의 가장 큰 장점입니다.