문제 정의
하나의 이진 배열(binary array)이 주어졌다고 가정해 봅시다. 목표는 배열에 있는 0 중 하나를 1로 바꿨을 때 가장 긴 연속된 1 시퀀스가 만들어지는 0의 위치(인덱스)를 찾는 것입니다.
예를 들어 입력이 [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]이라면 정답은 10입니다. 인덱스 10의 0을 1로 바꾸면 배열이 [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]이 되어, 인덱스 6부터 12까지 길이 7짜리 연속된 1 구간이 생깁니다.
알고리즘 접근 방식
이 문제는 배열을 단 한 번의 순회로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 각 0을 기준으로 왼쪽에 연속된 1의 개수(
count_left)와 오른쪽에 연속된 1의 개수(count_right)를 추적합니다. - 새로운 0을 만날 때마다 직전 0(
last_i)을 기준으로 "왼쪽 1 개수 + 오른쪽 1 개수 + 1(직전 0 자신)"이 현재 최댓값보다 크면 정답 후보를 갱신합니다. - 배열 끝까지 순회한 뒤에는 마지막 0에 대해서도 동일한 검사를 수행합니다.
- 교체할 수 있는 0이 전혀 없으면
-1을 반환합니다.
단계별 절차
- i := 0으로 초기화하고, n := 배열 A의 크기로 설정합니다.
- count_left := 0, count_right := 0으로 초기화합니다.
- max_i := -1, last_i := -1, count_max := 0으로 초기화합니다.
- i < n인 동안 다음을 반복합니다.
- A[i]가 1이면 count_right를 1 증가시킵니다.
- A[i]가 0이면:
- last_i가 -1이 아니라면, count_right + count_left + 1 > count_max일 때 count_max := count_left + count_right + 1로, max_i := last_i로 갱신합니다.
- last_i := i로 설정합니다.
- count_left := count_right로 옮긴 뒤, count_right := 0으로 초기화합니다.
- i를 1 증가시킵니다.
- 순회가 끝난 후에도 last_i가 -1이 아니라면, count_left + count_right + 1 > count_max일 때 count_max := count_left + count_right + 1로, max_i := last_i로 갱신합니다.
- max_i를 반환합니다.
파이썬 구현 예제
다음 코드를 통해 동작 과정을 더 잘 이해해 보겠습니다.
def find_max_one_index(A):
i = 0
n = len(A)
count_left = 0
count_right = 0
max_i = -1
last_i = -1
count_max = 0
while i < n:
if A[i] == 1:
count_right += 1
else:
if last_i != -1:
if count_right + count_left + 1 > count_max:
count_max = count_left + count_right + 1
max_i = last_i
last_i = i
count_left = count_right
count_right = 0
i += 1
if last_i != -1:
if count_left + count_right + 1 > count_max:
count_max = count_left + count_right + 1
max_i = last_i
return max_i
A = [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]
print(find_max_one_index(A))
실행 결과
입력
[1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]
출력
10
복잡도 분석
시간 복잡도: O(n) — 배열을 한 번만 순회하므로 입력 크기에 비례합니다.
공간 복잡도: O(1) — 상수 개의 변수만 사용하므로 추가 메모리가 거의 없습니다.