파이썬으로 'bird' 단어를 만들 수 있는 길이 4 부분 문자열 개수 세기

문제 개요

모든 문자가 소문자로 이루어진 문자열 S가 주어졌을 때, 각 문자를 임의로 재배열했을 때 단어 "bird"가 되는 길이 4짜리 부분 문자열(substring)이 몇 개 존재하는지 구하는 문제입니다.

예를 들어 입력 문자열이 "birdb"라면, 인덱스 0에서 시작하는 "bird"와 인덱스 2에서 시작하는 "rdbi"(재배열하면 bird) 두 곳이 조건을 만족하므로 출력은 2가 됩니다.

해결 접근 방법

핵심 아이디어는 간단합니다. 문자열을 처음부터 끝까지 순회하면서 길이 4짜리 윈도우를 하나씩 검사하고, 해당 윈도우에 'b', 'i', 'r', 'd'가 정확히 한 번씩 등장하는지 확인하면 됩니다.

알고리즘은 다음과 같이 진행됩니다.

카운터 변수 cnt = 0으로 초기화합니다.
i를 0부터 len(s) - 3까지 반복합니다. (길이 4짜리 부분 문자열의 시작 위치)
각 위치마다 크기 4의 카운트 배열 bird = [0, 0, 0, 0]을 만듭니다.
j를 i부터 i + 3까지 순회하면서 현재 문자에 따라 카운트를 증가시킵니다.
- s[j]가 'b'이면 bird[0] += 1
- s[j]가 'i'이면 bird[1] += 1
- s[j]가 'r'이면 bird[2] += 1
- s[j]가 'd'이면 bird[3] += 1
순회가 끝난 후 bird가 [1, 1, 1, 1]과 같다면, 네 문자가 모두 한 번씩 포함된 것이므로 cnt를 1 증가시킵니다.
모든 위치를 검사한 후 cnt를 반환합니다.

파이썬 구현 코드

def number_of_occurrence(s):
    cnt = 0
    for i in range(0, len(s) - 3):
        bird = [0, 0, 0, 0]
        for j in range(i, i + 4):
            if s[j] == 'b':
                bird[0] += 1
            elif s[j] == 'i':
                bird[1] += 1
            elif s[j] == 'r':
                bird[2] += 1
            elif s[j] == 'd':
                bird[3] += 1
        if bird == [1, 1, 1, 1]:
            cnt += 1
    return cnt

s = "birdb"
print(number_of_occurrence(s))

실행 결과

입력:

"birdb"

출력:

더 간결한 대안: Counter 활용

파이썬의 collections.Counter를 사용하면 위 로직을 훨씬 간결하게 표현할 수 있습니다.

from collections import Counter

def number_of_occurrence(s):
    target = Counter("bird")
    return sum(
        Counter(s[i:i+4]) == target
        for i in range(len(s) - 3)
    )

print(number_of_occurrence("birdb"))  # 출력: 2

두 방법 모두 시간 복잡도는 O(n × 4), 즉 O(n)으로 문자열 길이에 비례하여 선형적으로 동작합니다.

마무리

이 문제는 아나그램(anagram) 판별의 응용 형태로, 고정된 길이의 슬라이딩 윈도우 내에서 문자 빈도를 비교하는 전형적인 패턴을 연습하기에 좋은 예제입니다. 특정 단어뿐 아니라 임의의 단어에 대해서도 같은 방식을 그대로 확장해 적용할 수 있습니다.