문제

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

화단에 꽃을 심자. 인접한 plot 에 이미 꽃이 심어져있으면 다른 꽃을 심을 수 없다.
0,1 로 이루어진 배열이 주어지고, 0은 빈장소, 1은 꽃이 심어진 장소를 의미한다.
n 이 주어졌을때, n 만큼 꽃을 추가적으로 심을 수 있는지 확인하는 문제.

Constraints:

1 <= flowerbed.length <= 2 * 10^4
flowerbed[i] is 0 or 1.
There are no two adjacent flowers in flowerbed.
0 <= n <= flowerbed.length

풀이

function canPlaceFlowers(flowerbed: number[], n: number): boolean {

    let planted = 0;

    for (let i = 0; i < flowerbed.length; i++) {

        const left = flowerbed[i - 1] === undefined ? 0 : flowerbed[i - 1];
        const right = flowerbed[i + 1] === undefined ? 0 : flowerbed[i + 1];
        const current = flowerbed[i];

        if (left === 0 && right === 0 && current === 0) {
            flowerbed[i] = 1;
            planted++;
        }

        if (planted >= n) {
            return true
        }
    }

    return false;
};

매우 간단한 문제로 주어진 배열을 순회하면서 꽃을 심을 수 있는지 확인하면 된다.
꽃을 심을 수 있으면 배열의 원소를 1로 바꿔주자.
추가적으로 배열의 길이는 최대 2 * 10^4 까지 될 수 있으므로
최적화를 위해 심은 개수가 n 이상이되면 바로 true 리턴.

Cost

n = flowerbed.length
Time complexity = O(n)