Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 요소 하나를 삭제한 후 만들 수 있는 가장 긴 '1' 연속 부분 배열 찾기

문제 이해하기

0과 1로만 이루어진 이진 배열 nums가 주어지고, 배열에서 딱 한 개의 요소를 삭제할 수 있다고 가정해 보겠습니다. 이때 남은 배열에서 1로만 구성된 가장 긴 비어 있지 않은 연속 부분 배열(subarray)의 길이를 구하는 것이 목표입니다. 조건을 만족하는 부분 배열이 존재하지 않는다면 0을 반환합니다.

예를 들어 입력이 nums = [1,0,1,1,1,0,1,1,0]이라면 정답은 5입니다. 인덱스 5에 있는 0을 삭제하면 [1,1,1,1,1]이라는 다섯 개의 1이 연속된 구간을 얻을 수 있기 때문입니다.

알고리즘 접근 방법

핵심 아이디어는 배열을 순회하면서 연속된 1의 개수를 세어 별도의 리스트에 기록하고, 각 0을 기준으로 좌우의 1 구간 길이를 합산하여 최대값을 찾는 것입니다. 구체적인 단계는 다음과 같습니다.

  1. 예외 처리: 배열에 0이 전혀 없다면 어차피 한 개의 요소를 삭제해야 하므로 len(nums) - 1을 반환합니다. 반대로 1이 전혀 없다면 어떤 요소를 삭제해도 1로만 된 부분 배열을 만들 수 없으므로 0을 반환합니다.
  2. 구간 압축: 새 리스트 a와 카운터 cnt(초깃값 0)를 준비합니다. 배열을 처음부터 끝까지 순회하며 값이 1이면 cnt를 1씩 증가시킵니다. 값이 0을 만나면 그동안 세어 온 cnt를 a에 추가하고(cnt가 0이 아닐 때만), 0 자체도 a에 넣은 뒤 cnt를 초기화합니다.
  3. 마지막 구간 처리: 순회가 끝난 뒤 cnt가 0이 아니라면 마지막 연속 구간의 길이도 a에 추가합니다. 결과적으로 a는 "연속된 1의 개수"와 "0"이 번갈아 등장하는 형태가 됩니다.
  4. 최대 길이 탐색: Max를 0으로 초기화하고 리스트 a를 순회하며 각 0의 위치를 확인합니다.
    • a[i]가 0이 아니면 다음 요소로 넘어갑니다.
    • 0이 배열의 맨 끝에 있는 경우: 왼쪽 인접 값 a[i-1]과 Max를 비교해 더 큰 값을 저장합니다.
    • 0이 배열의 맨 앞에 있는 경우: 오른쪽 인접 값 a[i+1]과 Max를 비교합니다.
    • 0이 중간에 있는 경우: 이 0을 삭제하면 좌우의 1 구간이 하나로 합쳐지므로 a[i-1] + a[i+1]과 Max를 비교합니다.
  5. 결과 반환: 모든 위치를 확인한 뒤 Max를 반환합니다.

구현 코드

def solve(nums):
    # 0이 없으면 반드시 하나를 삭제해야 하므로
    if 0 not in nums:
        return len(nums) - 1
    # 1이 없으면 답은 0
    if 1 not in nums:
        return 0

    a = []      # 연속된 1의 개수와 0을 번갈아 저장할 리스트
    cnt = 0     # 현재 연속된 1의 개수

    for i in nums:
        if i == 0:
            if cnt != 0:
                a.append(cnt)
                cnt = 0
            a.append(i)
        else:
            cnt += 1

    if cnt != 0:
        a.append(cnt)

    Max = 0
    for i in range(len(a)):
        if a[i] != 0:
            continue
        if a[i] == 0 and i == len(a) - 1:   # 0이 맨 끝에 있는 경우
            Max = max(Max, a[i-1])
        elif a[i] == 0 and i == 0:          # 0이 맨 앞에 있는 경우
            Max = max(Max, a[i+1])
        elif a[i] == 0:                     # 0이 중간에 있는 경우
            Max = max(Max, a[i+1] + a[i-1])

    return Max


nums = [1, 0, 1, 1, 1, 0, 1, 1, 0]
print(solve(nums))

실행 결과

입력:

[1, 0, 1, 1, 1, 0, 1, 1, 0]

출력:

5

동작 과정 상세 분석

입력 [1,0,1,1,1,0,1,1,0]에 대해 리스트 a는 [1, 0, 3, 0, 2, 0]으로 구성됩니다. 각 0의 위치에서 계산되는 후보 길이는 다음과 같습니다.

  • 첫 번째 0(인덱스 1): 왼쪽 1개 + 오른쪽 3개 = 4
  • 두 번째 0(인덱스 3): 왼쪽 3개 + 오른쪽 2개 = 5
  • 세 번째 0(맨 끝, 인덱스 5): 왼쪽 2개 = 2

세 후보 중 가장 큰 값인 5가 최종 결과로 반환됩니다.

복잡도 분석

배열을 두 번 순회하므로 시간 복잡도는 O(n)이며, 압축된 구간 정보를 저장하기 위한 추가 리스트 때문에 공간 복잡도 역시 O(n)입니다. 참고로 슬라이딩 윈도우(sliding window) 기법을 활용하면 추가 리스트 없이 O(1) 공간으로도 동일한 문제를 해결할 수 있습니다.