Max Consecutive Ones

Q: Max Consecutive Ones의 시간 복잡도는 무엇인가요?

한 번만 순회하는 해법은 각 값을 한 번씩 읽으므로 O(n) 시간이 걸리고, 추가 공간은 O(1) 만 사용합니다. 현재 연속 구간을 위한 카운터 하나와 최댓값을 위한 카운터 하나입니다. 모든 원소가 1인 배열에서 매 인덱스마다 카운트를 다시 시작하면 O(n²) 시간이 걸립니다.

Q: 카운터가 1이 아니라 0으로 재설정되는 이유는 무엇인가요?

카운터에는 현재 인덱스에서 끝나는 연속 구간의 길이가 저장됩니다. 해당 위치의 값이 0 이면 그 위치에서 끝나는 1의 연속 구간이 없으므로 길이는 0 입니다. 다음 1이 그 값을 1 로 늘리며, 이는 새로운 연속 구간의 길이입니다.

Q: 연속된 최대 1의 개수는 슬라이딩 윈도우 문제인가요?

이를 하나로 볼 수 있습니다. 창에는 현재 구간이 담기고, 창의 오른쪽 끝은 값이 나올 때마다 이동하며, 0 이 나오면 왼쪽 끝이 그 위치를 지나도록 이동합니다. 창은 단계별로 줄어들지 않으므로, 두 끝 대신 카운터 하나를 사용하면 됩니다.

입문배열과 문자열

+10

모든 값이 0 또는 1인 배열 nums가 주어집니다. 연속 구간(run)은 사이에 0이 없이 서로 붙어 있는 1들의 구간입니다. 가장 긴 연속 구간의 길이를 반환하고, 배열에 1이 하나도 없으면 0을 반환하세요.

함수

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: 0과 1로 이루어진 배열
반환값integer: 연속된 1이 가장 길게 이어진 구간의 길이

제약 조건

1 ≤ nums.length ≤ 2 × 10⁴
모든 nums[i]는 0 또는 1입니다.

예제

입력: nums = [1, 1, 0, 1, 1, 1, 0, 1]
출력: 3
설명: 1은 세 개의 연속 구간을 이룹니다. 인덱스 0부터 1까지(길이 2), 3부터 5까지(길이 3), 그리고 인덱스 7만 있는 구간(길이 1)입니다. 가장 긴 구간의 길이는 3입니다.

입력: nums = [0, 1, 0, 1, 1]
출력: 2
설명: 인덱스 1의 단일 1은 인덱스 3과 4의 쌍에 지므로, 답은 2입니다.

입력: nums = [0, 0, 0]
출력: 0
설명: 어디에도 1이 없으므로 연속 구간이 없고 답은 0입니다.

후속 질문

최대 k개의 0을 1로 뒤집을 수 있다면 어떨까요? 가장 긴 연속 구간은 얼마나 길어질 수 있으며, 한 번의 순회로 여전히 찾을 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

0이 나타나는 순간 연속 구간이 끝나므로, 각 인덱스에서는 그 위치에서 끝나는 연속 구간의 길이만 알면 됩니다. 1이 나오면 증가하고 0이 나오면 초기화되는 카운터 하나로 한 번만 순회해 가장 긴 연속 구간을 찾을 수 있습니다.

모든 인덱스에서 앞으로 세기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

각 인덱스를 시작점으로 삼아 1이 보이는 동안 앞으로 이동해 보세요. 이동한 횟수가 그 지점에서 시작하는 연속 구간의 길이입니다. 가장 긴 연속 구간은 이 인덱스들 중 하나에서 시작하므로, 가장 큰 횟수가 답입니다.

이 이동들은 서로 겹칩니다. n개의 1로 이루어진 배열에서는 약 n² / 2번 이동하며, n = 2 × 10^4일 때 2 × 10^8번입니다.

알고리즘

best = 0으로 설정합니다.
모든 인덱스 start에 대해 length = 0으로 설정합니다.
start + length가 배열 안에 있고 nums[start + length]가 1인 동안 length에 1을 더합니다.
best와 length 중 더 큰 값을 유지합니다.
best를 반환합니다.

def findMaxConsecutiveOnes(nums):
    n = len(nums)
    best = 0
    for start in range(n):
        length = 0
        while start + length < n and nums[start + length] == 1:
            length += 1
        best = max(best, length)
    return best

누적 개수를 세며 한 번 순회하기

핵심 아이디어

현재 인덱스에서 끝나는 연속된 1의 길이인 current를 유지하세요. 1은 그 연속된 길이를 1만큼 늘리고, 0은 연속을 끊으므로 current는 0으로 떨어집니다. 각 연속 구간은 마지막 인덱스에서 측정되며, 이때 current는 구간의 전체 길이와 같으므로 current가 도달하는 가장 큰 값이 정답입니다.

[1, 1, 0, 1, 1, 1, 0, 1]에서 current는 1, 2, 0, 1, 2, 3, 0, 1의 값을 가지며, 가장 큰 값은 3입니다.

알고리즘

best = 0과 current = 0을 설정합니다.
nums의 각 값에 대해: 값이 1이면 current에 1을 더하고 best와 current 중 더 큰 값을 유지합니다.
값이 0이면 current = 0으로 설정합니다.
best를 반환합니다.

def findMaxConsecutiveOnes(nums):
    best = 0
    current = 0
    for x in nums:
        if x == 1:
            current += 1
            best = max(best, current)
        else:
            # A 0 breaks the run.
            current = 0
    return best

함정과 경계 사례

0을 만났을 때만 best를 업데이트하는 것. [0, 1, 1]처럼 끝까지 이어지는 연속 구간은 기록되지 않습니다. 매 1 뒤에 업데이트하거나, 루프가 끝난 뒤 한 번 더 비교하세요.
0에서 current를 초기화하지 않는 것. 서로 다른 연속 구간의 값이 합산되어 [1, 1, 0, 1, 1]은 4를 반환합니다.
best를 1 또는 nums[0]으로 시작하는 것. [0, 0, 0]은 0을 반환해야 합니다.
배열이 1부터 시작하는 Lua와 R에서 정방향 순회를 ≤ n 대신 < n으로 제한하는 것. 마지막 값을 읽지 않으므로 [0, 1]은 0을 반환합니다.

자주 묻는 질문3

Max Consecutive Ones의 시간 복잡도는 무엇인가요?

한 번만 순회하는 해법은 각 값을 한 번씩 읽으므로 O(n) 시간이 걸리고, 추가 공간은 O(1)만 사용합니다. 현재 연속 구간을 위한 카운터 하나와 최댓값을 위한 카운터 하나입니다. 모든 원소가 1인 배열에서 매 인덱스마다 카운트를 다시 시작하면 O(n²) 시간이 걸립니다.

카운터가 1이 아니라 0으로 재설정되는 이유는 무엇인가요?

카운터에는 현재 인덱스에서 끝나는 연속 구간의 길이가 저장됩니다. 해당 위치의 값이 0이면 그 위치에서 끝나는 1의 연속 구간이 없으므로 길이는 0입니다. 다음 1이 그 값을 1로 늘리며, 이는 새로운 연속 구간의 길이입니다.

연속된 최대 1의 개수는 슬라이딩 윈도우 문제인가요?

이를 하나로 볼 수 있습니다. 창에는 현재 구간이 담기고, 창의 오른쪽 끝은 값이 나올 때마다 이동하며, 0이 나오면 왼쪽 끝이 그 위치를 지나도록 이동합니다. 창은 단계별로 줄어들지 않으므로, 두 끝 대신 카운터 하나를 사용하면 됩니다.

def findMaxConsecutiveOnes(nums):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

nums = [1, 1, 0, 1, 1, 1, 0, 1]

예상 출력