Can Place Flowers — `O(n)` 그리디 스캔으로 인접 금지 배치 판정

꽃을 심을 수 있을까, 어떤 문제인가요?

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

정수 배열 flowerbed가 주어집니다. 0은 빈 자리, 1은 이미 꽃이 심어진 자리입니다. 꽃은 인접한 두 자리에 동시에 심을 수 없습니다. 새 꽃 n송이를 규칙을 위반하지 않고 심을 수 있으면 true를 반환하세요.

예시는 이렇습니다.

• flowerbed = [1, 0, 0, 0, 1], n = 1 → true (가운데 자리에 심을 수 있음)
• flowerbed = [1, 0, 0, 0, 1], n = 2 → false

제약은 다음과 같습니다.

• 1 <= flowerbed.length <= 2 * 10^4
• flowerbed[i]는 0 또는 1
• 입력 배열에 인접한 두 꽃은 없음 (초기 상태가 유효함)
• 0 <= n <= flowerbed.length

핵심 질문은 **"가능한 최대 배치 수가 n 이상인가"**입니다. 이 글에서는 왜 그리디가 최적인지부터, 배열을 수정하는 풀이와 수정하지 않는 풀이까지 정리합니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

Phase 1. 그리디가 왜 최적인가

"왼쪽부터 심을 수 있는 곳에 무조건 심는다"가 최적해를 놓치지 않는 이유를 따져 봅시다.

어떤 빈 자리 i에서 심을 수 있는데 건너뛰었다고 가정합니다. i에 심지 않으면 i + 2에 심을 수 있는 가능성이 새로 열릴까요? 그렇지 않습니다. i에 심어도 막히는 자리는 i + 1뿐이고, i를 건너뛰어도 i + 1에 심을 수 있는지는 i + 1 자체의 양쪽 이웃에 달려 있습니다.

다시 말해, 빈 자리를 건너뛰는 것이 이후에 더 많이 심을 수 있는 이득을 만들지 못합니다. "심을 수 있으면 바로 심는다"가 항상 최적이거나 최적과 동일한 결과를 냅니다. 이것이 **그리디 선택 속성(greedy choice property)**입니다.

건너뛴 경우:        [0, _, 0, 0, 0] → i를 비워 두면 i+2부터 동일
심은 경우:          [0, ✓, ×, 0, 0] → i+1만 막힘, i+2 이후는 동일

→ 건너뛰어도 이득이 없으므로, 심을 수 있으면 바로 심는 것이 최적

Phase 2. 배열을 수정하는 그리디 — 가장 직관적인 풀이

심은 자리를 1로 바꾸면, 다음 칸에서 "왼쪽에 꽃이 있는가?"를 배열 값으로 바로 확인할 수 있습니다.

fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
    var count = 0

    for (i in flowerbed.indices) {
        if (flowerbed[i] == 0) {
            val leftEmpty =
                (i == 0 || flowerbed[i - 1] == 0)
            val rightEmpty =
                (i == flowerbed.size - 1 || flowerbed[i + 1] == 0)

            if (leftEmpty && rightEmpty) {
                flowerbed[i] = 1
                count++
                if (count >= n) return true
            }
        }
    }
    return count >= n
}

[1, 0, 0, 0, 1], n = 1을 따라가 봅시다.

• i = 0: flowerbed[0] = 1 → 건너뜀
• i = 1: flowerbed[1] = 0, 왼쪽 flowerbed[0] = 1 → leftEmpty = false → 건너뜀
• i = 2: flowerbed[2] = 0, 왼쪽 flowerbed[1] = 0 ✓, 오른쪽 flowerbed[3] = 0 ✓ → 심음, count = 1 → count >= n → true

시간 O(len), 공간 O(1)입니다. 다만 **입력 배열을 직접 수정하는 부수 효과(side effect)**가 있습니다. 호출자가 원본 배열을 보존해야 한다면 문제가 될 수 있습니다.

Phase 3. 배열을 수정하지 않는 그리디 — 인덱스 건너뛰기

배열을 건드리지 않으려면, **"심은 직후에 다음 칸을 건너뛴다"**는 아이디어를 쓸 수 있습니다. 꽃을 심으면 바로 옆 칸은 어차피 심을 수 없으므로 i += 2로 점프합니다. 같은 원리로, 원래 꽃이 있는 자리(1)도 i += 2로 건너뜁니다.

fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
    var count = 0
    var i = 0

    while (i < flowerbed.size) {
        if (flowerbed[i] == 1) {
            i += 2
        } else if (i == flowerbed.size - 1 || flowerbed[i + 1] == 0) {
            count++
            i += 2
            if (count >= n) return true
        } else {
            i++
        }
    }
    return count >= n
}

분기는 세 가지입니다.

• flowerbed[i] == 1: 이미 꽃이 있으므로 i + 1은 확실히 심을 수 없음 → i += 2
• flowerbed[i] == 0이고 오른쪽이 비었음(i가 마지막이거나 flowerbed[i + 1] == 0): 심고 i += 2
• flowerbed[i] == 0이지만 오른쪽이 막혔음(flowerbed[i + 1] == 1): 심을 수 없음 → i++ (다음 칸에서 분기 1로 다시 건너뜀)

왼쪽은 왜 안 봐도 되나요?

이 풀이에서는 leftEmpty를 명시적으로 확인하지 않습니다. 대신 인덱스 점프가 왼쪽 안전성을 보장합니다.

• 꽃을 심은 뒤 i += 2: 바로 옆(i + 1)을 건너뛰므로, 도착한 i + 2의 왼쪽(i + 1)에는 꽃이 없습니다
• 원래 꽃(1) 뒤 i += 2: 초기 상태가 유효하므로 i + 1은 반드시 0입니다. 도착한 i + 2의 왼쪽(i + 1)도 비어 있습니다
• 오른쪽이 막혀서 i++: 현재 칸에 심지 않았으므로, 다음 칸의 왼쪽은 0(빈 칸 그대로)입니다

어떤 경로로 i에 도착하든 왼쪽이 이미 안전한 상태입니다. 그래서 오른쪽만 확인하면 됩니다.

같은 입력 [1, 0, 0, 0, 1], n = 1을 따라가 봅시다.

• i = 0: flowerbed[0] = 1 → i = 2
• i = 2: flowerbed[2] = 0, 오른쪽 flowerbed[3] = 0 ✓ → 심음, count = 1 → true

배열을 수정하지 않고 같은 결과를 냅니다. 시간 O(len), 공간 O(1)입니다.

참고: LeetCode 채점 환경에서는 입력 배열 수정 여부가 결과에 영향을 주지 않으므로, Phase 2의 풀이가 더 간결합니다. 하지만 실무 코드나 함수형 스타일을 선호한다면 Phase 3처럼 부수 효과를 피하는 편이 안전합니다.

엣지 케이스

이 문제에서 놓치기 쉬운 경계 조건을 정리합니다.

입력	n	결과	이유
[0]	1	true	양쪽 경계 모두 빈 것으로 취급
[1]	0	true	심을 필요가 없으면 항상 true
[0, 0, 0, 0, 0]	3	true	0번, 2번, 4번에 심음
[0, 0, 0, 0, 0]	4	false	최대 3송이만 가능
[1, 0, 0, 0, 0, 1]	1	true	2번 또는 3번에 심을 수 있음

n = 0일 때는 아무것도 심지 않아도 되므로 항상 true입니다. 코드에서 count >= n으로 비교하면 자연스럽게 처리됩니다.

두 풀이를 다시 비교

풀이	시간	공간	부수 효과	특징
배열 수정 그리디	O(len)	O(1)	입력 배열 변경	양쪽 이웃을 명시적으로 확인, 가장 읽기 쉬움
인덱스 건너뛰기 그리디	O(len)	O(1)	없음	점프 패턴이 왼쪽 안전성을 보장, 배열 불변

마무리

1. 그리디가 최적인 이유는 "빈 자리를 건너뛰어도 이후에 더 많이 심을 수 있는 이득이 없기 때문" — 심을 수 있으면 바로 심는 것이 항상 최적이거나 동일한 결과를 냅니다
2. 배열 수정 방식은 구현이 가장 간결하지만, 입력을 변경하는 부수 효과가 있다 — 원본 보존이 필요하면 인덱스 건너뛰기 방식이 안전합니다
3. 인덱스 건너뛰기의 핵심은 "꽃이 있으면 i += 2, 심으면 i += 2" — 어떤 경로로 도착하든 왼쪽이 안전한 상태가 유지되므로, 오른쪽만 확인하면 됩니다
4. 경계 처리가 이 문제의 실질적 난이도 — 첫 칸과 마지막 칸에서 "없는 이웃은 비어 있다"로 간주하는 조건이 빠지면 오답이 납니다