바이너리 문자열에서 1로 이루어진 연속 구간이 최대 하나인지 확인하는 파이썬 프로그램

문제 개요

앞에 불필요한 0이 붙지 않는 바이너리(2진) 문자열 s가 주어졌을 때, 이 문자열 안에서 숫자 1로만 이루어진 연속된 구간(segment)이 최대 한 개인지 확인해야 합니다.

예를 들어 입력이 s = "11100"이라면, 1로 이루어진 구간은 "111" 하나뿐이므로 결과는 True입니다. 반면 "10100"처럼 1 구간이 두 번 나타나면 False를 반환해야 합니다.

접근 방법

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

• count 변수를 -1로 초기화합니다. 이 값은 지금까지 등장한 0의 개수를 추적합니다.
• 문자열의 길이가 1이라면 어떤 문자든 구간이 하나뿐이므로 True를 반환합니다.
• 문자열의 각 문자를 순회하면서 다음을 검사합니다.
  • 현재 문자가 "1"인데 count가 -1보다 크다면, 즉 이미 0을 한 번 이상 지난 후라면 1 구간이 끊긴 뒤 다시 나타난 것이므로 False를 반환합니다.
  • 현재 문자가 "0"이라면 count를 1 증가시킵니다.
• 순회를 마칠 때까지 False가 반환되지 않았다면 True를 반환합니다.

예제 코드

def solve(s):
    count = -1
    if len(s) == 1:
        return True
    for i in s:
        if i == "1" and count > -1:
            return False
        elif i == "0":
            count += 1
    return True

s = "11100"
print(solve(s))

입력

11100

출력

True

동작 원리

count 변수는 사실상 "0이 처음 등장했는가"를 판단하는 기준점 역할을 합니다. 1로 이루어진 구간이 완전히 끝난 뒤, 즉 0이 한 번이라도 등장한 이후에 다시 1이 나타나면 그것은 두 번째 구간이므로 곧바로 False를 반환합니다. 반대로 모든 1이 문자열 앞부분에 몰려 있다면 True를 반환합니다.

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 저장 공간 없이 count 변수 하나만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 매우 긴 바이너리 문자열에도 효율적으로 적용할 수 있습니다.