실력키우기 소수문자열(C++)

1566 : 소수문자열

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 675 회    시도횟수: 2199 회   

문자열을 입력 받고, 그 문자열 중 어떤 한 문자라도 발생빈도가 소수를 만족하면 이는 소수문자열이라고 한다.

 

예를 들어 AABAAB는 소수문자열이다. A의 경우 4번 나타나며, B의 경우 2번 나타나기 때문에 이문자열은 소수문자열인 것이다.

 

10,000 이하의 문자열이 입력된다. 문자열은 알파벳 대문자만 구성된다.

입력에 대해서 해당 문자열이 소수문자열이 아닌 경우 "NONE"을 출력하며 소수문자열일 경우 소수문자열을 이루게 만들어주는 문자를 사전순으로 한 줄에 공백없이 출력한다.

[Copy] AABAAB

[Copy] B

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

/**************************************************************     Problem: 1566     User: a132034     Language: C++     Result: Success     Time:222 ms     Memory:1784 kb ****************************************************************/     #include    <iostream> #include    <stdio.h> #include    <string> #pragma warning(disable:4996) using namespace std; #define PRIME 1 static int primes[11111]; static int ALPHA[50]; int main() {     int length;     string str;           cin >> str;//입력받는다.     for (int i = 2; i <= str.length(); ++i)     {         bool flg = true;         for (int j = 2; j < i; ++j)         {             if (i%j == 0)                 flg = false;         }         if (flg)             primes[i] = PRIME;     }         for (int i = 0; i < str.length(); ++i)     {         ALPHA[str[i] - 'A']++;     }       bool none = false;     for (int i = 0; i < 26; ++i)     {         if (primes[ALPHA[i]] == PRIME)         {             printf("%c", i + 'A');             none = true;         }     }     if (!none)         printf("%s", "NONE"); }

약간 대충 짠 감이 있지만..

우선 문자열을 입력받은 후 최대 문자열만큼(한 문자만 계속 나올 경우) 소수가 나올 수 있으므로 

2부터 받은 문자열의 길이까지 소수를 primes 배열에 찾아서 넣어 주었다. (더 빠른 방법도 있으나 여기서는 크게 요구하지 않아서 그대로..)

ALPHA 배열에는 문자열을 하나씩 보면서 해당하는 알파벳 위치에 ++를 해주어 해당 알파벳이 몇 번 나왔는지 해당 위치에 체크하였다. 

아래부분은 만들어진 primes배열과 ALPHA배열을 조합하여 출력. 만약 출력할 것이 없다면 NONE 출력. 

간단한 예를 들자면 입력이 AABAAB일 경우

6까지 소수를 primes에 저장. 

primes : 0 0 1 1 0 1 0 (0부터 6까지)

받은 문자에 따라 ALPHA에 저장(A 4회 출현, B 2회 출현)

ALPHA : 4 2 0 0 0 0 0 0 0 0 0..... (배열을 50개로 넉넉히 잡아두었으나 사실 최대 알파벳 개수인 26개를 사용할 것.)

-> primes[ALPHA[i]] 이므로 

A의 경우 primes[4] -> 0이므로 소수가 아니다! 출력x

B의 경우 primes[2] -> 1(PRIME)이므로 소수! 출력한다.