Python으로 문자 하나를 삭제했을 때 모든 문자의 빈도가 같아지는지 확인하는 방법

소문자로만 이루어진 문자열 s가 주어졌을 때, 단 하나의 문자를 삭제한 후 모든 문자의 등장 빈도가 동일해지는지 확인하는 문제입니다.

예를 들어 입력이 s = "abbc"라면, 문자 'b' 중 하나를 제거하여 "abc"를 만들 수 있습니다. 이때 각 문자('a', 'b', 'c')의 빈도는 모두 1로 동일하므로 결과는 True가 됩니다.

해결 접근 방법

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

• 먼저 문자열 s에 포함된 각 문자와 그 빈도를 저장하는 맵(딕셔너리) occurrence를 만듭니다.
• 모든 문자의 빈도가 이미 동일하다면 True를 반환합니다.
• 그렇지 않다면, 문자열의 각 문자에 대해 다음을 반복합니다.
  • 해당 문자의 빈도를 1 감소시킵니다.
  • 이 상태에서 모든 문자의 빈도가 동일하다면 True를 반환합니다.
  • 동일하지 않다면 해당 문자의 빈도를 다시 1 증가시켜 원래 상태로 복원합니다.
• 모든 경우를 확인한 후에도 조건을 만족하지 않으면 False를 반환합니다.

구현 예제

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

from collections import defaultdict
def allSame(occurrence):
    counts = list(occurrence.values())
    return all(element == counts[0] for element in counts)
def solve(s):
    occurrence = defaultdict(int)
    for char in s:
        occurrence[char] += 1
    if allSame(occurrence):
        return True
    for char in s:
        occurrence[char] -= 1
        if allSame(occurrence):
            return True
        occurrence[char] += 1
    return False
s = "abbc"
print(solve(s))

입력

"abbc"

출력

True

코드 설명

allSame() 함수는 딕셔너리에 저장된 모든 빈도 값이 서로 같은지 검사합니다. solve() 함수는 먼저 각 문자의 빈도를 계산한 뒤, 이미 모든 빈도가 같은지 확인합니다. 만약 그렇지 않다면, 각 문자를 하나씩 임시로 제거해 보면서 조건이 충족되는지 검사하고, 어떤 경우에도 만족하지 못하면 최종적으로 False를 반환합니다. 이 알고리즘의 시간 복잡도는 O(n²)이며, 여기서 n은 문자열의 길이입니다.