Max Consecutive Ones — 한 번의 스캔으로 가장 긴 1 구간 찾기

가장 긴 연속된 1의 길이, 어떤 문제인가요?

LeetCode 485번 문제는 이렇게 주어집니다.

이진 배열 nums가 주어졌을 때, 배열 안에서 연속된 1의 최대 개수를 반환하세요.

예시는 이렇습니다.

• nums = [1, 1, 0, 1, 1, 1] → 3
• nums = [1, 0, 1, 1, 0, 1] → 2

제약은 다음과 같습니다.

• 1 <= nums.length <= 10^5
• nums[i]는 0 또는 1

이 문제의 핵심은 0이 구간의 끊김점이라는 점입니다. 1이 이어지는 동안 길이를 늘리고, 0을 만나면 현재 길이를 끊고 다시 시작하면 됩니다. 이 글에서는 각 위치에서 연속 구간을 다시 세는 느린 풀이부터, 한 번 순회하면서 현재 길이와 최댓값만 유지하는 O(n) 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

문제를 구간 길이 문제로 보기

입력 nums = [1, 1, 0, 1, 1, 1]를 보면:

[1, 1]   [1, 1, 1]
  길이 2     길이 3

0이 중간에서 구간을 끊습니다. 따라서 답은 각 1 구간 길이 중 최댓값인 3입니다.

즉 이 문제는 사실상:

0을 기준으로 나뉜 1 구간들의 길이 중 최댓값은?

를 묻는 문제입니다.

Phase 1. 각 위치에서 연속된 1의 길이를 다시 세기

가장 직관적인 방법은 배열의 각 위치를 시작점으로 보고, 거기서부터 연속된 1이 얼마나 이어지는지 매번 세는 것입니다.

fun findMaxConsecutiveOnes(nums: IntArray): Int {
    var answer = 0

    for (start in nums.indices) {
        if (nums[start] == 0) continue

        var length = 0
        var index = start

        while (index < nums.size && nums[index] == 1) {
            length++
            index++
        }

        answer = maxOf(answer, length)
    }

    return answer
}

nums = [1, 1, 0, 1, 1, 1]를 보면:

• start = 0 → 길이 2
• start = 1 → 길이 1
• start = 3 → 길이 3
• start = 4 → 길이 2
• start = 5 → 길이 1

정답은 맞지만 같은 구간을 여러 번 다시 셉니다. 예를 들어 마지막 [1, 1, 1] 구간은 start = 3, 4, 5에서 중복 계산됩니다.

최악의 경우 nums = [1, 1, 1, ..., 1]처럼 전부 1이면:

n + (n - 1) + (n - 2) + ... + 1

만큼 검사하게 되므로 시간 복잡도는 O(n²)입니다. 입력 길이가 최대 10^5이므로 이 방식은 적절하지 않습니다.

Phase 2. 한 번만 훑으면서 현재 길이와 최댓값 유지하기

중복 계산이 문제라면, 배열을 왼쪽에서 오른쪽으로 한 번만 보면서 현재 연속 길이만 유지하면 됩니다.

fun findMaxConsecutiveOnes(nums: IntArray): Int {
    var current = 0
    var answer = 0

    for (num in nums) {
        if (num == 1) {
            current++
            answer = maxOf(answer, current)
        } else {
            current = 0
        }
    }

    return answer
}

nums = [1, 1, 0, 1, 1, 1]를 따라가 봅시다.

num = 1 -> current = 1, answer = 1
num = 1 -> current = 2, answer = 2
num = 0 -> current = 0
num = 1 -> current = 1, answer = 2
num = 1 -> current = 2, answer = 2
num = 1 -> current = 3, answer = 3

최종 답은 3입니다.

이 풀이에서 변수 의미는 명확합니다.

• current: 지금 보고 있는 연속된 1 구간의 길이
• answer: 지금까지 본 구간들 중 최댓값

0을 만나면 현재 구간은 끝난 것이므로 current = 0으로 초기화합니다. 1을 만나면 현재 구간이 이어지므로 current++ 합니다.

시간 복잡도는 O(n)이고, 추가 공간은 O(1)입니다.

왜 0에서 길이를 0으로 리셋하면 되나요?

연속된 1의 길이를 세고 있으므로, 0을 만나는 순간 그 구간은 반드시 끝납니다.

예를 들어:

[1, 1, 0, 1]

여기서 세 번째 값 0은 앞의 [1, 1]과 뒤의 [1]을 이어 줄 수 없습니다. 따라서:

• 0 이전까지의 길이는 이미 answer에 반영되었고
• 새로운 구간은 0 다음부터 다시 시작해야 합니다

그래서 current = 0이 정확한 처리입니다.

이 문제는 값이 0 또는 1뿐이라 더 단순합니다. 다른 값이 섞인 문제였다면 "무엇이 구간을 끊는가"를 먼저 정의해야 합니다.

마지막이 1로 끝나도 괜찮나요?

괜찮습니다. answer를 1을 만날 때마다 바로 갱신하고 있기 때문입니다.

예를 들어:

nums = [1, 1, 1]

이라면:

1 -> current = 1, answer = 1
1 -> current = 2, answer = 2
1 -> current = 3, answer = 3

배열 끝에서 별도 후처리를 하지 않아도 됩니다. 만약 answer를 0을 만났을 때만 갱신하는 식으로 짰다면, 마지막 구간을 따로 처리해야 했을 것입니다. 현재 코드는 그럴 필요가 없습니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
[1]	1	길이 1의 유일한 구간
[0]	0	1 구간이 없음
[1, 1, 1]	3	전체가 하나의 구간
[0, 0, 0]	0	모든 값이 끊김점
[1, 1, 0, 1, 1, 1]	3	뒤쪽 구간이 더 김
[1, 0, 1, 1, 0, 1]	2	중간 구간이 최댓값

특히 [1, 1, 1]과 [0, 0, 0]을 같이 보는 것이 좋습니다. 하나는 끝까지 리셋 없이 이어지는 경우이고, 다른 하나는 한 번도 길이가 늘지 않는 경우입니다.

두 풀이를 다시 비교

풀이	시간	공간	특징
각 위치에서 구간 다시 세기	O(n²)	O(1)	직관적이지만 같은 구간을 반복 계산
한 번 순회하며 길이 유지	O(n)	O(1)	현재 구간 길이와 최댓값만 관리하면 충분

마무리

1. 이 문제는 가장 긴 연속 구간의 길이를 묻는 문제입니다 — 0은 구간을 끊고, 1은 구간을 이어 줍니다
2. 같은 구간을 여러 번 다시 세면 O(n²)가 됩니다 — 전부 1인 입력에서 비효율이 바로 드러납니다
3. 현재 구간 길이 current와 최댓값 answer만 유지하면 O(n)에 해결됩니다 — 배열을 한 번만 훑으면 됩니다
4. 0을 만나면 current = 0으로 리셋하면 됩니다 — 연속 조건이 끊겼기 때문입니다
5. answer를 1을 볼 때마다 갱신하면 마지막 구간도 별도 처리 없이 포함됩니다 — 끝이 1로 끝나는 입력도 자연스럽게 처리됩니다