Max Consecutive Ones

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

한 번 순회하는 해법은 각 값을 정확히 한 번씩 읽기 때문에 O(n) 시간이 걸립니다. 추가 공간은 O(1) 을 사용합니다. 현재 연속 구간을 위한 카운터 하나와 최댓값을 위한 카운터 하나입니다. 모든 값이 1인 배열에서 각 인덱스마다 카운트를 다시 시작하면 O(n²) 시간이 걸립니다.

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

카운터는 현재 인덱스에서 끝나는 연속 구간의 길이를 저장합니다. 현재 값이 0 이면 그 위치에서 끝나는 1의 연속 구간이 없으므로 길이는 0 입니다. 다음 1이 나오면 값이 1 로 증가하며, 이는 새로운 연속 구간의 올바른 길이입니다.

Q: 이것은 슬라이딩 윈도우 문제인가요?

이를 하나의 창으로 볼 수 있습니다. 창에는 현재 구간이 들어 있고, 오른쪽 경계는 값이 들어올 때마다 이동하며, 0 이 나오면 왼쪽 경계가 그 너머로 이동합니다. 여기서는 창을 단계별로 줄일 필요가 없으므로, 두 경계 대신 카운터 하나만 사용하면 됩니다. 최대 k 개의 0을 1로 뒤집을 수 있는 더 어려운 버전에서는 창 관점이 유용합니다.

Q: 0 하나를 뒤집을 수 있다면 연속된 1의 개수를 어떻게 세나요?

두 개의 카운터를 유지하세요. 하나는 여기서 끝나는 뒤집기 없이 연속된 구간의 길이이고, 다른 하나는 뒤집기를 한 번 사용한 구간의 길이입니다. 1에서는 두 카운터 모두 1씩 증가합니다. 0에서는 뒤집기를 사용한 카운터가 일반 카운터에 1을 더한 값이 되고, 일반 카운터는 0으로 초기화됩니다. 한 번만 순회하면서 확인한 뒤집기 사용 카운터 중 가장 큰 값이 답입니다.

입문배열과 문자열

+10

모든 값이 0 또는 1인 배열 nums가 주어집니다. 연속 구간은 그 사이에 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입니다.

제출 시 숨은 테스트 +14개

후속 질문

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

힌트

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

3개 중 0개 열림

풀이

0이 나타나는 순간 연속 구간이 끝나므로, 각 인덱스에서 알아야 할 것은 그 위치에서 끝나는 연속 구간의 길이뿐입니다. 매 인덱스마다 처음부터 다시 세면 같은 작업을 계속 반복하게 됩니다. 1이 나오면 증가하고 0이 나오면 초기화되는 카운터 하나로 한 번만 순회하면서 답을 구할 수 있습니다.

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

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

핵심 아이디어

모든 연속 구간은 어딘가에서 시작합니다. 따라서 각 인덱스를 시작점으로 시도하고 1이 계속 나타나는 동안 앞으로 이동하세요. 이때 이동한 단계 수가 해당 위치에서 시작하는 연속 구간의 길이입니다. 모든 시작점에서 센 값 중 가장 큰 값이 정답입니다. [1, 1, 0, 1, 1, 1, 0, 1]에서 인덱스 3에서 시작하면 인덱스 6의 0을 만날 때까지 1을 세 번 지나가므로, 결과는 3입니다.

가장 긴 연속 구간은 시도하는 인덱스 중 하나에서 시작하고, 그 첫 인덱스부터 이동하면 그 길이를 정확히 측정하므로 정답입니다.

비용은 중복 계산에서 발생합니다. n개의 1이 있는 배열에서 인덱스 0에서 시작하면 n번 이동하고, 다음 인덱스에서는 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

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

핵심 아이디어

배열을 한 번 순회하면서 current를 유지합니다. current는 현재 인덱스에서 끝나는 1의 연속 길이입니다. 1을 만나면 연속 구간이 이어지므로 current가 1 증가합니다. 0을 만나면 연속 구간이 끝나므로 current를 다시 0으로 설정합니다. 1을 만날 때마다 current와 best를 비교합니다.

[1, 1, 0, 1, 1, 1, 0, 1]에서 current는 1, 2, 0, 1, 2, 3, 0, 1의 값을 가지며, 이 중 가장 큰 값은 3입니다. 각 연속 구간은 마지막 인덱스에서 측정되며, 이때 current는 연속 구간의 전체 길이와 같으므로 지금까지 확인한 최댓값이 가장 긴 연속 구간의 길이입니다.

각 값을 한 번씩 읽으므로 시간 복잡도는 O(n)이고, 메모리에는 정수 두 개만 있으면 됩니다.

알고리즘

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, 1, 0, 1, 1]에 대해 4를 반환합니다.
best를 1이나 nums[0]으로 초기화하는 경우입니다. 0만 있는 배열은 0을 반환해야 합니다.
Lua와 R에서는 배열 인덱스가 1부터 시작하므로, 앞으로 순회할 때 < n 대신 start + length ≤ n을 확인합니다.

자주 묻는 질문4

Max Consecutive Ones의 시간 복잡도는 얼마인가요?

한 번 순회하는 해법은 각 값을 정확히 한 번씩 읽기 때문에 O(n) 시간이 걸립니다. 추가 공간은 O(1)을 사용합니다. 현재 연속 구간을 위한 카운터 하나와 최댓값을 위한 카운터 하나입니다. 모든 값이 1인 배열에서 각 인덱스마다 카운트를 다시 시작하면 O(n²) 시간이 걸립니다.

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

카운터는 현재 인덱스에서 끝나는 연속 구간의 길이를 저장합니다. 현재 값이 0이면 그 위치에서 끝나는 1의 연속 구간이 없으므로 길이는 0입니다. 다음 1이 나오면 값이 1로 증가하며, 이는 새로운 연속 구간의 올바른 길이입니다.

이것은 슬라이딩 윈도우 문제인가요?

이를 하나의 창으로 볼 수 있습니다. 창에는 현재 구간이 들어 있고, 오른쪽 경계는 값이 들어올 때마다 이동하며, 0이 나오면 왼쪽 경계가 그 너머로 이동합니다. 여기서는 창을 단계별로 줄일 필요가 없으므로, 두 경계 대신 카운터 하나만 사용하면 됩니다. 최대 k개의 0을 1로 뒤집을 수 있는 더 어려운 버전에서는 창 관점이 유용합니다.

0 하나를 뒤집을 수 있다면 연속된 1의 개수를 어떻게 세나요?

두 개의 카운터를 유지하세요. 하나는 여기서 끝나는 뒤집기 없이 연속된 구간의 길이이고, 다른 하나는 뒤집기를 한 번 사용한 구간의 길이입니다. 1에서는 두 카운터 모두 1씩 증가합니다. 0에서는 뒤집기를 사용한 카운터가 일반 카운터에 1을 더한 값이 되고, 일반 카운터는 0으로 초기화됩니다. 한 번만 순회하면서 확인한 뒤집기 사용 카운터 중 가장 큰 값이 답입니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

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

기대값