파이썬으로 한 쌍의 비트를 교환한 후 가장 긴 연속된 1의 길이 구하기

이진 문자열 s가 주어졌다고 가정해 보겠습니다. 문자열 안에서 최대 한 쌍의 문자를 서로 교환할 수 있을 때, 그 결과로 만들 수 있는 가장 긴 연속된 1(연속 부분 문자열)의 길이를 구하는 것이 목표입니다.

문제 예시

예를 들어 입력이 s = "1111011111"이라면 출력은 9가 됩니다. 인덱스 4의 '0'과 인덱스 9의 '1'을 서로 교환하면 9개의 연속된 1을 얻을 수 있기 때문입니다.

접근 방법: 슬라이딩 윈도우

이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 왼쪽 포인터 l, 오른쪽 포인터 r, 그리고 윈도우 내 '0'의 개수를 세는 cnt를 사용합니다.
• 윈도우 안에 '0'이 2개 이상 존재하면, 왼쪽 끝 문자를 제거하며(l 증가) 윈도우를 축소합니다. 한 번의 교환만 허용되므로 '0'은 최대 1개까지만 유지합니다.
• 매 단계마다 현재 윈도우의 길이 (r - l + 1)로 정답 ans를 갱신합니다.

알고리즘 단계

1. l := 0, cnt := 0, ans := 0으로 초기화합니다.
2. r을 0부터 문자열 길이까지 반복합니다.
   • s[r]이 '0'이면 cnt를 1 증가시킵니다.
   • cnt > 1이면, s[l]이 '0'일 경우 cnt를 감소시키고 l을 1 증가시킵니다.
   • ans를 max(ans, r - l + 1)로 갱신합니다.
3. 마지막으로 min(ans, 문자열 내 1의 개수)를 반환합니다. 실제 1의 개수보다 길어질 수 없기 때문입니다.

구현 코드

아래는 위 알고리즘을 파이썬으로 구현한 예제입니다.

class Solution:
   def solve(self, s):
      l = 0
      cnt = 0
      ans = 0
      for r in range(len(s)):
         cnt += s[r] == "0"
         if cnt > 1:
            cnt -= s[l] == "0"
            l += 1
         ans = max(ans, r - l + 1)
      return min(ans, s.count("1"))
ob = Solution()
s = "1111011111"
print(ob.solve(s))

입력

"1111011111"

출력

9

복잡도 분석

이 풀이는 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 공간은 상수만 사용하므로 공간 복잡도는 O(1)입니다. 문자열이 매우 긴 경우에도 효율적으로 동작합니다.