정수 값으로 이루어진 배열 arr[]가 주어졌을 때, 나머지 모든 요소의 합을 나눌 수 있는 요소가 몇 개인지 계산하는 것이 이번 문제의 목표입니다.
배열은 동일한 자료형의 요소들을 고정된 크기로 순차적으로 저장할 수 있는 대표적인 자료구조입니다. 데이터 집합을 하나의 이름으로 관리할 수 있으며, 같은 타입의 변수 여러 개를 묶어 놓은 컬렉션으로 이해하면 쉽습니다.
예시
입력 − int arr_1[] = {9, 6, 3}
출력 − 개수는 3설명 − 요소 3을 제외한 나머지 합은 9+6=15로 3으로 나누어 떨어지고, 요소 6을 제외한 합은 9+3=12로 6으로 나누어 떨어지며, 요소 9를 제외한 합은 6+3=9로 9로 나누어 떨어집니다. 따라서 개수는 3입니다.
입력 − arr[] = {3, 10, 4, 6, 7}
출력 − 개수는 3설명 − 요소 3을 제외한 합은 10+4+6+7=27로 3으로 나누어 떨어지고, 요소 10을 제외한 합은 3+4+6+7=20으로 10으로 나누어 떨어지며, 요소 6을 제외한 합은 3+10+4+7=24로 6으로 나누어 떨어집니다. 따라서 개수는 3입니다.
프로그램에 적용한 접근 방식
배열 arr[]를 생성합니다.
length() 함수를 사용해 배열의 길이를 구합니다. 이 함수는 배열에 포함된 요소 수에 해당하는 정수 값을 반환합니다.
조건을 만족하는 요소의 개수를 저장할 임시 변수를 선언합니다.
i를 0부터 시작해 배열 크기보다 작은 동안 반복하는 바깥쪽 루프를 실행합니다.
루프 안에서 임시 변수 temp를 0으로 초기화합니다.
j를 0부터 시작해 배열 크기보다 작은 동안 반복하는 안쪽 루프를 실행합니다.
i와 j가 같으면 현재 요소 자신이므로 continue로 건너뜁니다.
그렇지 않으면 temp = temp + arr[j]로 나머지 요소들의 합을 누적합니다.
temp % arr[i] == 0인지 검사하여 참이면 count를 1 증가시킵니다.
count를 반환합니다.
결과를 출력합니다.
예제 코드
#include <iostream>
using namespace std;
int countelements( int arr_1[], int size){
// 조건을 만족하는 숫자의 개수를 저장
int result = 0;
for (int i = 0; i < size; i++){
// 합계를 0으로 초기화
int sum = 0;
for (int j = 0; j < size; j++){
if (i == j){
continue;
}
else{
sum += arr_1[j];
}
}
// 합이 선택한 요소로 나누어 떨어지는 경우
if (sum % arr_1[i] == 0){
result++;
}
}
// 개수 반환
return result;
}
// main 함수
int main(){
int arr_1[] = { 1, 2, 3, 4, 5, 6 };
int size = sizeof(arr_1) / sizeof(arr_1[0]);
cout <<"count is " <<countelements(arr_1, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
count is 2
시간 복잡도 개선 팁
위 방식은 이중 반복문을 사용하기 때문에 시간 복잡도가 O(n²)입니다. 전체 합을 미리 한 번 계산해 두면, 각 요소에 대해 "전체 합 − 현재 요소"만 나눗셈으로 확인하면 되므로 시간 복잡도를 O(n)까지 줄일 수 있습니다.
int countElementsFast(int arr[], int size){
long long total = 0;
for (int i = 0; i < size; i++){
total += arr[i]; // 전체 합을 미리 계산
}
int result = 0;
for (int i = 0; i < size; i++){
long long rest = total - arr[i]; // 현재 요소를 제외한 합
if (rest % arr[i] == 0){
result++;
}
}
return result;
}두 코드 모두 배열 {1, 2, 3, 4, 5, 6}에 대해 동일하게 "count is 2"를 출력합니다. 실제로 1을 제외한 합 20은 1로, 3을 제외한 합 18은 3으로 나누어 떨어지므로 조건을 만족하는 요소는 1과 3 두 개뿐입니다.