Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 문자열의 ASCII 값 합이 소수인지 판별하는 방법

문제 개요

이 문제에서는 하나의 문자열이 주어지며, 문자열을 구성하는 모든 문자의 ASCII 값의 합이 소수(prime number)인지 아닌지를 판별하여 그 결과를 YES / NO 형태로 출력해야 합니다.

먼저 핵심 개념부터 간단히 정리해 보겠습니다.

  • ASCII 값: 컴퓨터가 문자를 숫자로 표현하기 위해 사용하는 문자 인코딩 체계입니다. 예를 들어 영문 대문자 'A'는 65, 소문자 'a'는 97에 해당합니다.
  • 소수(Prime Number): 1과 자기 자신만을 약수로 가지는 수입니다. 즉, 2, 3, 5, 7, 11처럼 1보다 크면서 다른 수로 나누어 떨어지지 않는 수를 의미합니다.

예시로 이해하기

입력: string = "Hello"
출력: No

위 예시에서 "Hello"라는 문자열의 각 문자('H', 'e', 'l', 'l', 'o')의 ASCII 값을 모두 더한 결과가 소수가 아니기 때문에 출력은 "No"가 됩니다.

해결 접근 방법

이 문제를 해결하는 과정은 다음과 같이 두 단계로 나눌 수 있습니다.

  1. 문자열의 모든 문자를 순회하면서 각 문자의 ASCII 값을 더하여 총합(sum)을 구합니다.
  2. 구한 총합이 소수인지 여부를 판별합니다.

소수 판별은 단순히 2부터 (sum-1)까지 모두 나누어 보는 방법도 있지만, 아래 코드에서 사용한 것처럼 6k ± 1 최적화 기법을 활용하면 √sum까지만 검사하면 되므로 훨씬 효율적입니다.

C++ 구현 코드

#include <iostream>
using namespace std;
bool CheckPrimeString(string str) {
   int len = str.length(), sum = 0;
   // 1단계: 모든 문자의 ASCII 값 합산
   for (int i = 0; i < len; i++)
   sum += (int)str[i];
   // 2단계: 소수 판별
   if (sum<= 1)
      return false;
   if (sum <= 3)
      return true;
   if (sum % 2 == 0 || sum % 3 == 0)
      return false;
   for (int i = 5; i * i <= sum; i = i + 6)
      if (sum % i == 0 || sum % (i + 2) == 0)
   return false;
   return true;
}
int main() {
   string str = "Hello!";
   cout<<"The string '"<<str<<" ' is ";
   if (CheckPrimeString(str))
      cout<<"a prime String \n";
   else
      cout<<"not a prime String\n";
}

실행 결과

The string 'Hello! ' is not a prime String

코드 설명

CheckPrimeString 함수는 먼저 반복문을 통해 문자열의 각 문자를 정수형으로 변환하여 ASCII 값을 누적합니다. 이후 다음 순서로 소수 여부를 검사합니다.

  • 합이 1 이하이면 소수가 아니므로 false를 반환합니다.
  • 합이 2 또는 3이면 소수이므로 true를 반환합니다.
  • 합이 2나 3으로 나누어 떨어지면 소수가 아니므로 false를 반환합니다.
  • 마지막으로 5부터 시작해 6씩 증가시키며 i와 i+2로 나누어 떨어지는지 검사합니다. 이는 모든 소수가 6k±1 형태라는 성질을 활용한 최적화입니다.

모든 검사를 통과하면 해당 합은 소수이므로 true를 반환하고, main 함수에서는 이 결과에 따라 적절한 메시지를 출력합니다.

시간 복잡도

문자열 길이를 n, ASCII 값의 합을 s라고 할 때, 합산 과정은 O(n), 소수 판별은 O(√s)의 시간 복잡도를 가집니다. 따라서 전체 시간 복잡도는 O(n + √s)로 매우 효율적입니다.