LeetCode | Easy | 605. Can Place Flowers

LeetCode | Easy | 605. Can Place Flowers

Problems

• 📘 Src: LeetCode
• 🗂️ Cat: Greedy

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 true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

Constraints

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

Examples

flowerbed	n	result
[1, 0, 0, 0, 1]	1	true
[1, 0, 0, 0, 1]	2	false

Solutions

• ⏳ TC: O(n)
• 💾 SC: O(1)

class Solution {

    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0; // 새로운 꽃을 심을 수 있는 위치의 수를 셀 변수

        for (int i = 0; i < flowerbed.length; i++) {
            // 현재 위치와 양쪽 위치가 모두 비어 있는 경우
            if (flowerbed[i] == 0 &&
                (i == 0 || flowerbed[i - 1] == 0) &&
                (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {

                // 꽃을 심고 count 증가
                flowerbed[i] = 1;
                count++;

                // n개의 꽃을 모두 심을 수 있으면 true 반환
                if (count >= n) {
                    return true;
                }
            }
        }

        // 모든 위치를 검사한 후에도 n개의 꽃을 심을 수 없으면 false 반환
        return count >= n;
    }
}

Approaches

이 문제는 주어진 flowerbed에 n개의 꽃을 인접한 꽃 없이 심을 수 있는지를 판단하는 문제입니다. 그리디 알고리즘을 사용하여 각 위치에 꽃을 심을 수 있는지 확인하고, 가능한 경우 꽃을 심고 그 수를 증가시킵니다. 이 과정을 flowerbed의 모든 위치에 대해 반복하여, n개의 꽃을 모두 심을 수 있으면 true를, 그렇지 않으면 false를 반환합니다.

주어진 flowerbed를 순회하며 다음과 같은 조건을 확인합니다:

• 현재 위치가 빈 칸 flowerbed[i] == 0 인지 확인합니다.
• 현재 위치의 왼쪽과 오른쪽이 모두 비어 있는지 확인합니다.
  • 현재 위치가 flowerbed의 처음이나 끝일 경우, 해당 위치는 양쪽이 비어 있는 것으로 간주합니다.
• 조건을 만족하면 해당 위치에 꽃을 심고, 꽃을 심은 위치를 1로 표시합니다.
• 꽃을 심은 횟수를 증가시킵니다.
• n개의 꽃을 모두 심을 수 있으면 즉시 true를 반환합니다.

이 과정의 시간 복잡도는 flowerbed 배열의 길이에 비례하여 O(n)이며, 추가적인 메모리 사용 없이 입력 배열만 수정하기 때문에 공간 복잡도는 O(1)입니다.