[LeetCode] 605. Can Place Flowers - 문제풀이

Description

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.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false

Constraints:

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

Solution 1. Greedy Algorithm(탐욕법)

public boolean canPlaceFlowers(int[] flowerbed, int n) {

    if(n ==0)return true;
    int len = flowerbed.length;
    int plantCnt = 0;

    int prev = 0;
    for (int i = 0; i < len; i++) {
        int next = i == len-1? 0 : flowerbed[i+1];
        if(prev == 0 && next ==0 && flowerbed[i] ==0){
            flowerbed[i] = 1;
            if(++plantCnt == n){
                return true;
            }
        }
        prev = flowerbed[i];
    }
    return false;
}

탐욕 알고리즘을 통해 앞에서 부터 스캔하며 꽃 심는게 가능할 때 마다 심어주며 plantCnt를 늘려나가고 주어진 n개만큼 심었을때 true를 반환하고 끝까지 진행했는데 n개에 미치지 못하면 false를 반환합니다. 꽃은 이전요소, 현재요소, 다음 요소 모두 0일때만 심을 수 있으며 각 배열이 모서리는 0으로 쳐서 계산합니다.

• 시간복잡도 : O(n)
• 공간복잡도 : O(1)

Reference

Can Place Flowers - LeetCode