파이썬으로 이진 문자열을 두 부분으로 나눠 최대 점수 구하기

문제 개요

이진 문자열(binary string) s가 주어졌다고 가정해 봅시다. 이 문자열을 두 개의 비어 있지 않은 부분 문자열 s1과 s2로 분할하는 연산을 수행합니다. 이때 분할 점수는 다음과 같이 계산됩니다.

점수 = s1에 포함된 '0'의 개수 + s2에 포함된 '1'의 개수

우리의 목표는 가능한 모든 분할 지점 중에서 얻을 수 있는 최대 점수를 찾는 것입니다.

예시

입력이 s = "011001100111"이라면, 문자열을 "01100" + "110111"과 같이 나눌 수 있습니다. 이 경우 왼쪽 부분에 '0'이 3개, 오른쪽 부분에 '1'이 5개 있으므로 점수는 3 + 5 = 8이 되며, 이것이 최대값입니다.

풀이 접근 방법

이 문제는 그리디하게 한 번의 순회로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 먼저 전체 문자열에서 '1'의 총 개수를 세어 ones에 저장합니다.
• 왼쪽부터 차례대로 각 위치를 기준으로 분할 지점을 시뮬레이션하면서, 현재 문자가 '0'이면 zeros를 1 증가시키고, '1'이면 ones를 1 감소시킵니다.
• 각 단계마다 ones + zeros 값이 현재까지의 최대 답보다 크면 갱신합니다.
• 마지막 인덱스는 제외해야 합니다. 두 부분 문자열이 모두 비어 있지 않아야 하기 때문입니다.

알고리즘 단계

• ones ← 문자열 s에서 '1'의 개수
• zeros ← 0
• ans ← 0
• i를 0부터 len(s) - 2까지 반복:
  • s[i]가 '0'이면 zeros를 1 증가
  • 그렇지 않으면 ones를 1 감소
  • ans ← max(ans, ones + zeros)
• ans 반환

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

구현 코드

def solve(s):
   ones = s.count("1")
   zeros = 0
   ans = 0
   for i in range(len(s) - 1):
      if s[i] == "0":
         zeros += 1
      else:
         ones -= 1
      ans = max(ans, ones + zeros)
   return ans

s = "011001100111"
print(solve(s))

입력

"011001100111"

출력

8

마무리

이 문제는 누적 카운팅(cumulative counting) 기법을 활용한 대표적인 슬라이딩 분할 문제입니다. '1'의 전체 개수를 미리 구해 둔 뒤, 분할 지점을 왼쪽에서 오른쪽으로 이동하면서 조건에 맞게 카운터만 업데이트하면 O(n) 시간 안에 정답을 구할 수 있습니다. 실제 코딩 테스트에서도 자주 등장하는 유형이므로 패턴을 익혀두면 유용합니다.