Python으로 이진 문자열의 모든 1이 등거리에 있는지 확인하는 방법

이진 문자열이 주어졌을 때, 문자열 안에 있는 모든 1이 서로 등거리(equidistant)에 있는지 확인해야 합니다. 다시 말해, 임의로 선택한 두 개의 1 사이 거리가 항상 같아야 한다는 의미입니다. 단, 입력 문자열에는 최소 두 개 이상의 1이 포함되어 있다고 가정합니다.

예를 들어 입력이 s = "100001000010000"라고 해보겠습니다. 이 경우 1들이 각각 4칸씩 떨어져 있으므로 출력은 True가 됩니다.

문제 해결 접근 방식

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

• 1의 위치를 저장할 새로운 리스트 index를 생성합니다.
• 인덱스 i를 0부터 문자열 길이까지 순회하면서, s[i]가 '1'이면 해당 인덱스 i를 리스트 끝에 추가합니다.
• 리스트의 크기를 t에 저장합니다.
• 인접한 두 1의 거리 차이(index[i] - index[i-1])가 첫 번째 간격(index[1] - index[0])과 일치하지 않으면 False를 반환합니다.
• 모든 간격이 일치하면 True를 반환합니다.

구현 예제

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

def solve(s):
    index = []
    for i in range(len(s)):
        if s[i] == '1':
            index.append(i)
    t = len(index)
    for i in range(1, t):
        if (index[i] - index[i - 1]) != (index[1] - index[0]):
            return False
    return True

s = "100001000010000"
print(solve(s))

입력

"100001000010000"

출력

True

복잡도 분석

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 또한 1의 위치를 저장하기 위해 리스트를 사용하므로 공간 복잡도 역시 최악의 경우 O(n)입니다.

마무리

핵심 아이디어는 문자열에 등장하는 모든 1의 위치를 먼저 기록한 뒤, 인접한 위치 간의 간격이 모두 동일한지 비교하는 것입니다. 이 방법은 코드가 간결하고 직관적이며, 다양한 이진 문자열 패턴 문제에 응용할 수 있습니다.