BOJ 2153 - 소수 단어

문제

알파벳으로 이루어진 단어에서 소문자는 1~~26, 대문자는 27~~52의 값을 갖는다. 각 문자 값의 합이 소수이면 소수 단어이다.

입력

알파벳 문자열이 주어진다.

출력

소수 단어이면 "It is a prime word.", 아니면 "It is not a prime word."를 출력한다.

예제

입력	출력
`UFRN`	`It is a prime word.`

풀이

각 문자의 값을 합산하고 소수 판별을 수행한다.

소문자는 c - 'a' + 1, 대문자는 c - 'A' + 27로 값을 계산한다
모든 문자의 값을 합산한다
2부터 sqrt(합) 까지 나누어떨어지는지 확인하여 소수를 판별한다
결과에 따라 지정된 문장을 출력한다

핵심 아이디어: 문자 값의 범위가 1~52이고 문자열 길이가 짧으므로, 합은 작은 수이고 소수 판별은 O(sqrt(S))에 빠르게 수행된다.

코드

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main()
{
  string word;
  cin >> word;
 
  int count = 0;
  int len = word.length();
  for (int i = 0; i < len; i++)
  {
    if (word[i] >= 'a' && word[i] <= 'z')
    {
      count += (int)(word[i] - 'a' + 1);
    }
    else if (word[i] >= 'A' && word[i] <= 'Z')
    {
      count += (int)(word[i] - 'A' + 27);
    }
  }
 
  bool flag = 0;
  for (int i = 2; i * i <= count; i++)
  {
    if (count % i == 0)
    {
      flag = 1;
      break;
    }
  }
 
  if (flag)
  {
    cout << "It is not a prime word.";
  }
  else
  {
    cout << "It is a prime word.";
  }
 
  return 0;
}

복잡도

시간: O(N + sqrt(S)) (N: 문자열 길이, S: 문자 값 합)
공간: O(1)

문제