문제 개요
이진 문자열(binary string) s가 주어졌다고 가정해 보겠습니다. 우리는 최대 한 개의 "0"을 "1"로 뒤집을 수 있으며, 이 조건에서 만들 수 있는 가장 긴 연속된 1의 부분 문자열 길이를 구하는 것이 목표입니다.
예를 들어 입력이 s = "1010110001"이라면, 인덱스 3에 있는 0을 뒤집아 "1011110001"을 만들 수 있습니다. 이 문자열에서 가장 긴 연속된 1의 길이는 4이므로, 출력 결과는 4가 됩니다.
접근 방법: 슬라이딩 윈도우
이 문제는 슬라이딩 윈도우(Sliding Window), 즉 투 포인터 기법을 사용하면 선형 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 왼쪽 포인터(left)와 오른쪽 포인터(right)로 탐색 범위(윈도우)를 관리합니다.
- 윈도우 내부의 1의 개수(ones)를 실시간으로 추적합니다.
- 윈도우 전체 크기에서 1의 개수를 빼면 0의 개수가 되는데, 이 값이 1을 초과하면 왼쪽 포인터를 이동시켜 윈도우를 축소합니다.
- 매 단계마다 윈도우 크기의 최대값을 정답(ans)으로 갱신합니다.
알고리즘 단계
- n := 문자열 s의 길이
- ans := 0, ones := 0, left := 0, right := 0으로 초기화
- right < n인 동안 다음을 반복:
- s[right]가 "1"이면 ones를 1 증가
- (right − left + 1 − ones) > 1, 즉 윈도우 내 0의 개수가 2개 이상이면:
- s[left]가 "1"이라면 ones를 1 감소
- left를 1 증가시켜 윈도우 축소
- ans와 현재 윈도우 크기(right − left + 1) 중 더 큰 값을 ans에 저장
- right를 1 증가
- 반복이 끝나면 ans 반환
구현 예제
다음 파이썬 코드를 통해 위 알고리즘을 확인해 보겠습니다.
def solve(s):
n = len(s)
ans = ones = left = right = 0
while right < n:
if s[right] == "1":
ones += 1
while right - left + 1 - ones > 1:
remove = s[left]
if remove == "1":
ones -= 1
left += 1
ans = max(ans, right - left + 1)
right += 1
return ans
s = "1010110001"
print(solve(s))입력
"1010110001"
출력
4
복잡도 분석
오른쪽 포인터와 왼쪽 포인터가 각각 문자열을 최대 한 번씩만 순회하므로, 시간 복잡도는 O(n)입니다. 추가적인 자료구조 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다.