문제 개요
대문자와 소문자가 혼합된 임의의 길이를 가진 문자열이 주어졌을 때, 그중 ASCII 값이 소수(prime)인 문자의 개수를 계산하는 것이 이번 문제의 목표입니다.
알파벳의 ASCII 코드 값은 다음과 같은 범위를 가집니다.
- 대문자 [A-Z]: 65 ~ 90
- 소문자 [a-z]: 97 ~ 122
예시
입력 string str = "Aebg"
출력 개수는 2
설명 — A의 ASCII 값은 65로 소수가 아니므로 제외되고, e는 101로 소수이므로 포함됩니다. b는 66으로 소수가 아니며, g는 103으로 소수이므로 포함됩니다. 따라서 ASCII 값이 소수인 문자는 총 2개입니다.
입력 — string str = "GOXFH"
출력 — 개수는 2
설명 — G는 71(소수), O는 79(소수), X는 88(소수 아님), F는 70(소수 아님), H는 72(소수 아님)입니다. 따라서 ASCII 값이 소수인 문자는 총 2개입니다.
해결 접근 방법
문자열을 입력받아 변수(예: str)에 저장합니다.
length() 함수를 사용하여 문자열의 길이를 구합니다. 이 함수는 공백을 포함한 문자 수를 정수 값으로 반환합니다.
소수 여부를 판별할 함수를 선언하여 각 문자를 검사할 때 활용합니다.
i를 0부터 문자열 길이까지 반복하며 순회합니다.
반복문 안에서 현재 문자의 ASCII 값이 소수인지 확인하고, 소수라면 카운트를 1 증가시키고 아니라면 그대로 둡니다.
총 카운트 값을 반환합니다.
결과를 출력합니다.
C++ 구현 예제
아래 코드는 에라토스테네스의 체(Sieve of Eratosthenes)를 활용하여 257 이하의 모든 소수를 미리 구해 둔 뒤, 문자열을 한 번만 순회하면서 각 문자의 ASCII 값이 소수인지 빠르게 판별합니다. 덕분에 매번 나눗셈으로 소수를 검사하는 것보다 훨씬 효율적입니다.
#include <iostream>
#include <vector>
using namespace std;
#define max_val 257
// 문자열에서 ASCII 값이 소수인 문자의 개수를 찾는 함수
int countprime(string str){
// 'max_val' 이하의 소수를 찾기 위해 에라토스테네스의 체 사용
// 불리언 배열 "prime[0..n]"에서 prime[i]는
// i가 소수가 아니면 false, 소수이면 true가 됨
vector<bool> prime(max_val + 1, true);
// 0과 1은 소수가 아님
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= max_val; p++){
// prime[p]가 변경되지 않았다면 p는 소수
if (prime[p] == true) {
// p의 모든 배수를 소수가 아닌 것으로 표시
for (int i = p * 2; i <= max_val; i += p){
prime[i] = false;
}
}
}
int result = 0;
// 문자열 전체를 순회
for (int i = 0; i < str.length(); ++i){
if (prime[int(str[i])]){
result++;
}
}
return result;
}
// 메인 함수
int main(){
string str = "tutorialspoint";
// 결과 출력
cout <<"count is: "<< countprime(str);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
count is: 1
"tutorialspoint" 문자열에서 ASCII 값이 소수인 문자는 'a'(ASCII 값 97) 하나뿐입니다. 나머지 문자들의 ASCII 값은 모두 합성수이기 때문에 카운트되지 않습니다.