파이썬으로 연산 적용 후 최대 이진 문자열 구하기

이진 문자열(binary string)이 하나 주어져 있다고 가정해 봅시다. 우리는 다음 두 가지 연산을 원하는 만큼 몇 번이든 적용할 수 있습니다.

문자열에 부분 문자열 "00"이 포함되어 있다면, 이를 "10"으로 바꿀 수 있습니다.
문자열에 부분 문자열 "10"이 포함되어 있다면, 이를 "01"로 바꿀 수 있습니다.

목표는 이러한 연산을 임의의 횟수만큼 수행한 뒤 얻을 수 있는 문자열 중, 수치적으로 가장 큰(최대인) 이진 문자열을 찾는 것입니다.

예를 들어 입력이 s = "001100"이라면 출력은 111011이 됩니다. 아래와 같은 과정을 거쳐 변환할 수 있기 때문입니다.

(00)1100 -> 101(10)0 -> 1010(10) -> 10(10)01 -> 100(10)1 -> 1(00)011 -> 111011

접근 방법

이 문제를 해결하기 위해 다음 단계를 따릅니다.

length := 문자열 s의 길이
zeros := s에 포함된 '0'의 개수
만약 zeros < 2라면, 연산으로 더 이상 개선할 수 없으므로 s를 그대로 반환합니다.
s := s의 왼쪽 끝에 연속된 모든 '1'을 제거합니다.
leading_ones := length - (제거 후 s의 길이)
leading_ones := leading_ones + zeros - 1
trailing_ones := length - leading_ones - 1
answer_left := '1'을 leading_ones개 이어 붙인 문자열
answer_right := '1'을 trailing_ones개 이어 붙인 문자열
answer_left + '0' + answer_right를 연결하여 반환합니다.

여기서 핵심 아이디어는 다음과 같습니다. "00" -> "10" 연산은 0을 1로 바꿀 수 있는 유일한 방법이며, "10" -> "01" 연산은 1을 오른쪽으로 밀어내는 역할을 합니다. 이 두 연산을 조합하면 맨 앞의 0부터 차례대로 1로 만들 수 있고, 결과적으로 딱 하나의 0만 남기고 나머지는 모두 1로 채운 형태가 최댓값이 됩니다.

예제 코드

아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.

def solve(s):
    length = len(s)
    zeros = s.count('0')
    if zeros < 2:
        return s
    s = s.lstrip('1')
    leading_ones = length - len(s)
    leading_ones += zeros - 1
    trailing_ones = length - leading_ones - 1
    answer_left = '1' * leading_ones
    answer_right = '1' * trailing_ones
    return ''.join([answer_left, '0', answer_right])

s = "001100"
print(solve(s))

입력

"001100"