문제 소개
정수 배열이 주어졌을 때, 각 숫자의 자릿수 합(digit sum)이 소수(prime)가 되는 원소만 찾아 출력하는 것이 이번 문제의 목표입니다. 만약 조건을 만족하는 숫자가 하나도 없다면 -1을 반환하면 됩니다.
입력 · 출력 예시
입력: arr[] = {2, 4, 3, 19, 25, 6, 11, 12, 18, 7}
출력: 2, 3, 25, 11, 12, 7결과에 포함된 숫자들을 살펴보면 그 기준을 쉽게 이해할 수 있습니다. 2, 3, 7은 한 자리 숫자로서 그 자체가 소수이므로 자릿수 합 역시 소수입니다. 두 자리 숫자 중에서는 25(2+5=7), 11(1+1=2), 12(1+2=3)처럼 각 자릿수를 모두 더한 값이 소수가 되는 숫자만 해당됩니다. 반면 19는 1+9=10으로 소수가 아니기 때문에 결과에서 제외됩니다.
접근 방법 및 알고리즘
이 문제는 크게 두 가지 하위 작업으로 나눌 수 있습니다.
- 자릿수 합 계산: 숫자를 10으로 나눈 나머지(% 10)를 반복해서 더하고, 몫을 새로운 값으로 사용하여 모든 자릿수를 더합니다.
- 소수 판별: 2부터 √n까지의 수로 나누어 떨어지는지 확인합니다. 나누어 떨어지는 수가 하나도 없으면 소수입니다.
전체 처리 흐름은 다음과 같습니다.
- 정수 배열을 준비하고, sizeof(arr)/sizeof(arr[0])로 배열의 크기(m)를 구합니다.
- 배열의 각 요소에 대해 자릿수 합을 계산합니다.
- 계산된 자릿수 합이 소수인지 검사합니다.
- 소수라면 해당 배열 요소를 출력하고, 끝까지 조건을 만족하는 요소가 없었다면 -1을 출력합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
// 소수 판별 함수
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
// 자릿수 합 계산 함수
int digitSum(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
int main() {
int arr[] = {2, 4, 3, 19, 25, 6, 11, 12, 18, 7};
int m = sizeof(arr) / sizeof(arr[0]);
bool found = false;
for (int i = 0; i < m; i++) {
if (isPrime(digitSum(arr[i]))) {
cout << arr[i] << " ";
found = true;
}
}
// 조건을 만족하는 숫자가 없으면 -1 출력
if (!found) cout << -1;
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
2 3 25 11 12 7
마무리 및 복잡도 분석
이 풀이의 시간 복잡도는 배열의 길이를 n, 숫자의 최대 자릿수를 d, 원소의 최댓값을 v라고 할 때 대략 O(n × (√v + d))입니다. 각 숫자마다 자릿수 합을 구하는 데 O(d), 소수 여부를 확인하는 데 O(√v)가 소요되기 때문입니다. 특히 소수 판별 시 검사 범위를 √n까지만 제한하면 불필요한 나눗셈 연산을 크게 줄일 수 있으므로, 이 최적화 기법을 함께 기억해 두면 유용합니다.