Python으로 문자열 내 모든 문자의 빈도가 소수인지 확인하는 방법

문자열 s가 주어졌을 때, 문자열에 등장하는 각 문자의 빈도(출현 횟수)가 모두 소수인지 확인해야 합니다.

예를 들어 입력이 s = "apuuppa"라면 결과는 True입니다. 'a'는 2번, 'p'는 3번, 'u'는 2번 등장하며, 2와 3은 모두 소수이기 때문입니다.

문제 해결 접근 방법

• 먼저 각 문자와 그 빈도수를 저장하는 맵(freq)을 생성합니다.
• 맵에 있는 각 문자에 대해 다음을 검사합니다.
  • 빈도수가 0보다 크고, 그 값이 소수가 아니라면 False를 반환합니다.
• 모든 문자의 빈도수가 소수라면 True를 반환합니다.

소수 판별 함수

isPrime 함수는 1보다 큰 수에 대해 2부터 num-1까지 차례대로 나누어 떨어지는지 확인합니다. 나누어 떨어지는 수가 하나라도 있으면 소수가 아니므로 False를 반환하고, 끝까지 통과하면 True를 반환합니다. 1 이하의 값은 소수가 아니므로 False를 반환합니다.

예제 코드

from collections import defaultdict

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def solve(s):
    freq = defaultdict(int)

    for i in range(len(s)):
        freq[s[i]] += 1

    for char in freq:
        if freq[char] > 0 and isPrime(freq[char]) == False:
            return False

    return True

s = "apuuppa"
print(solve(s))

입력

"apuuppa"

출력

True

코드 설명 및 개선 팁

defaultdict(int)는 존재하지 않는 키에 접근할 때 자동으로 기본값 0을 생성해 주기 때문에, 별도의 초기화 과정 없이 빈도수를 손쉽게 누적할 수 있습니다.

또한 collections.Counter를 사용하면 빈도 계산 부분을 한 줄로 줄일 수 있습니다.

from collections import Counter

def solve(s):
    freq = Counter(s)
    return all(isPrime(v) for v in freq.values())

시간 복잡도 측면에서, 문자열 길이를 n이라 하면 빈도 계산은 O(n), 각 빈도수에 대한 소수 판별은 최악의 경우 O(m)(m은 빈도수)이므로 전체적으로 매우 효율적인 편입니다. 소수 판별 시 √num까지만 검사하면 성능을 더욱 개선할 수 있습니다.