Python으로 이진 문자열에 m개의 연속된 1 또는 0이 있는지 확인하는 방법

문제 개요

이진 문자열 s와 정수 m이 주어졌을 때, 해당 문자열 안에 m개의 연속된 1 또는 m개의 연속된 0이 존재하는지 확인해야 하는 문제입니다.

예를 들어 입력이 s = "1110111000111", m = 3이라면, 문자열에 세 개의 연속된 0("000")과 세 개의 연속된 1("111")이 모두 존재하므로 결과는 True가 됩니다.

해결 접근 방식

이 문제는 문자열을 한 번만 순회하면서 현재 위치까지 이어진 연속 문자의 개수를 추적하는 방식으로 효율적으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.

str_size에 문자열 s의 길이를 저장합니다.
count_0과 count_1을 0으로 초기화합니다.
i를 0부터 str_size - 2까지 반복하면서 다음을 수행합니다.
- s[i]가 '0'이면 count_1을 0으로 초기화하고 count_0을 1 증가시킵니다.
- 그렇지 않으면(즉, s[i]가 '1'이면) count_0을 0으로 초기화하고 count_1을 1 증가시킵니다.
- count_0 또는 count_1이 m과 같아지면 True를 반환합니다.
반복이 끝날 때까지 조건이 만족되지 않으면 False를 반환합니다.

구현 예제

def solve(s, m):
    str_size = len(s)
    count_0 = 0
    count_1 = 0
    for i in range(0, str_size - 1):
        if (s[i] == '0'):
            count_1 = 0
            count_0 += 1
        else :
            count_0 = 0
            count_1 += 1
        if (count_0 == m or count_1 == m):
            return True
    return False

s = "1110111000111"
m = 3
print(solve(s, m))

입력

"1110111000111", 3

출력

True

동작 원리

이 알고리즘의 핵심은 새로 등장한 문자가 이전 문자와 다를 때마다 반대쪽 카운터를 리셋한다는 점입니다. 예를 들어 '0'을 만나면 1의 연속이 끊기므로 count_1을 0으로 만들고, count_0만 증가시킵니다. 이렇게 하면 어느 시점에서든 count 값이 곧 현재 진행 중인 연속 구간의 길이를 의미하게 됩니다.

시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다. 여기서 n은 문자열의 길이입니다.

대체 방법: itertools.groupby 활용

파이썬 표준 라이브러리의 itertools.groupby를 사용하면 더 파이썬다운 코드로 같은 문제를 해결할 수 있습니다. groupby는 인접한 동일 문자들을 하나의 그룹으로 묶어주므로, 각 그룹의 길이만 비교하면 됩니다.

from itertools import groupby

def solve(s, m):
    for _, group in groupby(s):
        if sum(1 for _ in group) >= m:
            return True
    return False

s = "1110111000111"
m = 3
print(solve(s, m))  # True

두 방법 모두 동일한 결과를 반환하지만, 직접 카운터를 관리하는 첫 번째 방식은 알고리즘의 흐름을 명확히 보여주고, groupby를 사용하는 두 번째 방식은 코드가 간결하고 가독성이 높다는 장점이 있습니다.