문제 설명
N개의 정수로 이루어진 배열이 주어졌을 때, 각 요소의 합이 N으로 나누어 떨어지는 비어 있지 않은 부분 집합을 찾아야 합니다. 조건을 만족하는 부분 집합이 존재한다면, 해당 부분 집합의 크기와 함께 원본 배열에서의 인덱스를 출력해야 합니다.
예를 들어 입력 배열이 [3, 2, 7, 1, 9]이고 N = 5라고 가정해 보겠습니다. 첫 번째와 두 번째 요소를 선택하면 3 + 2 = 5이므로 5로 나누어 떨어집니다. 따라서 출력은 다음과 같습니다.
2
1 2
해결 접근 방식
이 문제는 접두사 합(prefix sum)과 나머지 연산을 활용하면 선형 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열을 순회하면서 지금까지의 누적 합을 N으로 나눈 나머지를 계산합니다.
- 순회 중 나머지가 0이 되는 순간이 있다면, 처음부터 해당 위치까지의 요소들이 곧 정답 부분 집합입니다.
- 동일한 나머지가 두 번 등장한다면, 두 위치 사이에 있는 요소들의 합은 반드시 N으로 나누어 떨어집니다. 비둘기집 원리에 의해 N개의 접두사 합에 대해 가능한 0이 아닌 나머지는 N-1개뿐이므로, 이러한 경우는 반드시 존재합니다.
알고리즘 단계
- 나머지 값을 저장할 맵(my_map)을 하나 정의합니다.
- 누적 합 변수 add를 0으로 초기화합니다.
- i를 0부터 N-1까지 반복하며 다음을 수행합니다.
- add := (add + arr[i]) mod N 으로 갱신합니다.
- add가 0이라면 크기(i + 1)와 인덱스 1 ~ i+1을 출력하고 함수를 종료합니다.
- add가 이미 my_map에 존재한다면 크기(i - my_map[add])와 인덱스 my_map[add]+2 ~ i+1을 출력하고 함수를 종료합니다.
- 그렇지 않다면 my_map[add] := i 로 현재 나머지와 위치를 저장합니다.
C++ 구현 예제
아래 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void subset_find(int arr[], int N) {
unordered_map<int, int> my_map;
int add = 0;
for (int i = 0; i < N; i++) {
add = (add + arr[i]) % N;
if (add == 0) {
cout << i + 1 << endl;
for (int j = 0; j <= i; j++)
cout << j + 1 << " ";
return;
}
if (my_map.find(add) != my_map.end()) {
cout << (i - my_map[add]) << endl;
for (int j = my_map[add] + 1; j <= i; j++)
cout << j + 1 << " ";
return;
}
else
my_map[add] = i;
}
}
int main() {
int arr[] = {3, 2, 7, 1, 9};
int N = sizeof(arr) / sizeof(arr[0]);
subset_find(arr, N);
}
입력
{3, 2, 7, 1, 9}출력
2
1 2
복잡도 분석
시간 복잡도: O(N) — 배열을 한 번만 순회하면 됩니다.
공간 복잡도: O(N) — 최악의 경우 모든 나머지 값을 맵에 저장해야 할 수 있습니다.