[LeetCode] 605. Can Place Flowers - Java

https://leetcode.com/problems/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

---

풀이

풀이 과정

꽃이 심어져 있거나 비어있는 화단의 배열 flowerbed와 심어야할 꽃의 개수 n이 주어진다.

연속한 화단에 꽃을 심을 수 없다고 할 때 현재 화단에 주어진 개수 만큼의 꽃을 심을 수 있는지 구하는 문제이다.

먼저 심어야 할 꽃이 없는 경우에는 바로 true를 return해 준다.

// 심어야 할 꽃이 없는 경우 바로 true를 return
if(n == 0) return true;

 

이후 화단을 차례대로 탐색한다.
현재 화단이 비어있는 경우는 다음 세가지 경우에 따라 꽃을 심을 수 있는지 없는지 체크한다.

1. 첫 번째 화단인 경우
flowerbed의 길이가 1이거나 오른쪽 화단이 비어있는 경우 꽃을 심을 수 있다.

// 첫 화단인 경우
if(i == 0) {
    // flowerbed의 길이가 1이거나 오른쪽 화단이 비어있는 경우
    if(flowerbed.length == 1 || flowerbed[i + 1] == 0) {
        // 현재 화단에 꽃을 심음
        flowerbed[i] = 1;
        // 심어야할 꽃의 수 감소
        n--;
    }
}

 

2. 마지막 화단인 경우
왼쪽 화단이 비어있는 겨웅 꽃을 심을 수 있다.

// 마지막 화단인 경우
else if(i == flowerbed.length - 1) {
    // 왼쪽 화단이 비어있는 경우
    if(flowerbed[i - 1] == 0) {
    /// 현재 화단에 꽃을 심음
        flowerbed[i] = 1;
        // 심어야할 꽃의 수 감소
        n--;
    }
}

 

3. 나머지 화단인 경우
좌우의 화단이 모두 비어있는 경우 꽃을 심을 수 있다.

// 나머지 화단인 경우
else {
    // 좌우의 화단이 모두 비어있는경우
    if(flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
        // 현재 화단에 꽃을 심음
        flowerbed[i] = 1;
        // 심어야할 꽃의 수 감소
        n--;
    }
}

 

현재 화단을 탐색한 후 심어야 할 꽃의 수가 0이 되는 경우 true를 return한다.

// 심어야할 꽃의 수가 0이 되는 경우 true를 return
if(n == 0) return true;

 

모든 탐색이 종료된 후 남은 꽃의 수가 0인 경우에는 true, 0보다 큰 경우에는 false를 return 한다.

// 남은 꽃의 수가 0인 경우 true, 0보다 큰 경우 false를 return
return (n == 0) ? true : false;

---

최종 코드

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        // 심어야 할 꽃이 없는 경우 바로 true를 return
        if(n == 0) return true;

        for(int i = 0; i < flowerbed.length; i++) {
            // 현재 화단이 비어있는 경우
            if(flowerbed[i] == 0){
                // 첫 화단인 경우
                if(i == 0) {
                    // flowerbed의 길이가 1이거나 오른쪽 화단이 비어있는 경우
                    if(flowerbed.length == 1 || flowerbed[i + 1] == 0) {
                        // 현재 화단에 꽃을 심음
                        flowerbed[i] = 1;
                        // 심어야할 꽃의 수 감소
                        n--;
                    }
                }
                // 마지막 화단인 경우
                else if(i == flowerbed.length - 1) {
                    // 왼쪽 화단이 비어있는 경우
                    if(flowerbed[i - 1] == 0) {
                    /// 현재 화단에 꽃을 심음
                        flowerbed[i] = 1;
                        // 심어야할 꽃의 수 감소
                        n--;
                    }
                }
                // 나머지 화단인 경우
                else {
                    // 좌우의 화단이 모두 비어있는경우
                    if(flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
                        // 현재 화단에 꽃을 심음
                        flowerbed[i] = 1;
                        // 심어야할 꽃의 수 감소
                        n--;
                    }
                }
            }
            // 심어야할 꽃의 수가 0이 되는 경우 true를 return
            if(n == 0) return true;
        }

        // 남은 꽃의 수가 0인 경우 true, 0보다 큰 경우 false를 return
        return (n == 0) ? true : false;
    }
}

---