Python으로 특정 문자의 빈도가 문자열 길이의 절반을 넘는지 확인하는 방법

소문자, 대문자, 숫자, 특수문자가 섞여 있는 문자열 s가 주어졌다고 가정해 봅시다. 이때 특정 하나의 문자가 문자열 전체 길이의 절반보다 더 많이 등장하는지 확인해야 합니다.

예를 들어 입력이 s = "CC*Ca5&CC"라면 출력은 True가 됩니다. 문자 'C'의 등장 횟수는 5회이고, 문자열의 길이는 9이기 때문입니다. 즉, 5 > 9/2 조건을 만족합니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• freq := 문자열 s에 포함된 각 문자의 빈도를 저장하는 맵(딕셔너리) 생성
• freq의 각 문자 ch에 대해 반복
  • 만약 ch의 빈도가 (문자열 길이 / 2)보다 크다면
    • True 반환
• 모든 문자를 확인한 후에도 조건을 만족하지 않으면 False 반환

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

예제 코드

from collections import defaultdict

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

    for ch in s:
        freq[ch] += 1

    for ch in freq:
        if freq[ch] > len(s) // 2:
            return True

    return False

s = "CC*Ca5&CC"
print(solve(s))

입력

"CC*Ca5&CC"

출력

True

코드 설명

위 코드에서는 defaultdict(int)를 사용하여 각 문자의 등장 횟수를 손쉽게 집계합니다. 먼저 문자열을 한 번 순회하며 빈도를 계산한 뒤, 다시 딕셔너리를 순회하면서 어떤 문자의 빈도라도 len(s) // 2(정수 나눗셈)보다 크면 즉시 True를 반환합니다. 시간 복잡도는 O(n)으로 매우 효율적이며, 공간 복잡도 역시 문자 종류 수에 비례하므로 O(k)입니다.