Python으로 이진 문자열의 0과 1이 번갈아 나오도록 재배열 가능한지 확인하는 방법

길이가 2 이상인 이진 문자열 s가 주어졌다고 가정해 봅시다. 우리의 목표는 이 문자열의 문자들을 재배열하여 0과 1이 서로 번갈아 나타나도록 만들 수 있는지 확인하는 것입니다.

예를 들어, 입력이 s = "1000111"이라면, 이 문자열을 재배열하여 "1010101"을 만들 수 있으므로 결과는 True가 됩니다.

문제 해결 접근 방법

0과 1이 번갈아 나오는 문자열은 길이에 따라 두 가지 조건으로 나뉩니다.

• 문자열의 길이가 짝수인 경우: 0과 1의 개수가 정확히 같아야 합니다.
• 문자열의 길이가 홀수인 경우: 0과 1의 개수 차이가 정확히 1이어야 합니다.

이를 바탕으로 문제는 다음 단계로 해결할 수 있습니다.

• 이진 문자열 s에서 1의 개수(one_count)를 셉니다.
• 이진 문자열 s에서 0의 개수(zero_count)를 셉니다.
• s의 길이가 짝수라면, one_count와 zero_count가 같을 때 true를 반환하고, 그렇지 않으면 false를 반환합니다.
• s의 길이가 홀수라면, |one_count − zero_count|가 1일 때 true를 반환하고, 그렇지 않으면 false를 반환합니다.

예제 코드

다음 구현을 통해 더 잘 이해해 보겠습니다.

def solve(s):
    one_count = s.count('1')
    zero_count = s.count('0')
    if len(s) % 2 == 0:
        return (one_count == zero_count)
    return abs(one_count - zero_count) == 1

s = "1000111"
print(solve(s))

입력

"1000111"

출력

True

복잡도 분석

이 알고리즘은 문자열을 한 번 순회하면서 0과 1의 개수를 세므로 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 또한 추가적인 저장 공간을 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다.