[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 inadjacent 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

💭 Questions for solving

• 어떤 경우에(조건) 꽃을 심을 수 있지?
• i==0 또는 i==len(flowerbed)-1인 경우는?

내가 시도한 접근 방법

• 🔵 planted 변수: previous flowerbed에 꽃이 심겨 있는지 상태

---

• 🔴flowerbed[i]==0 인 경우,
  (1) planted=False 인 경우:
  1. 꽃 심기
  2. planted 상태 update(planted=True)
  (2) planted=True 인 경우
  1. 꽃 심을 수 없다
  2. planted 상태 update(platend=False)

---

• 🔴flowerbed[i]==1 인 경우,
  1. planted 상태 update(planted=True)

💻 첫 번째 시도

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        i=0
        planted=False
        
        while i<len(flowerbed):
            if flowerbed[i]==1:
                planted=True
            else:
                if not planted:
                    # print("because not planted, let's plant")
                    n-=1
                    planted=True
                else: planted=False
            
            i+=1
                   
        return True if n==0 else False

But 통과 못함. Why???

• 아래 Approach-1 가 내가 시도한 방법이랑 유사하다.
• 내가 놓친 부분은 planted=True 인 경우, flowerbed[i]==1 이면 꽃을 잘못 심은 것이기 때문에 n을 update 해주어야 한다.(n+=1)

💻 두 번째 시도 - 통과

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        i=0
        planted=False
        
        while i<len(flowerbed):
            if flowerbed[i]==1:
                if planted: n+=1  # 새로 추가된 if문!
                planted=True
            else:
                if not planted and n>0:
                    # print("because not planted, let's plant")
                    n-=1
                    planted=True
                else: 
                    planted=False
            i+=1
                   
        return True if n==0 else False

🕐 Complexity

• Time complexity: O(n).
  사이즈가 n인 flowerbed 리스트를 scan한다.
• Space complexity: O(1).
  Constant extra space is used.

💊 Approach-1

class Solution(object):
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count, prev = 0, 0

        for cur in flowerbed:
            if cur == 1:
                if prev == 1: # violation!
                    count -= 1
                prev = 1
            else:
                if prev == 1: # can't plant
                    prev = 0 
                else:
                    count += 1
                    prev = 1 # the cur plot gets taken
            
        return count >= n

💊 Approach-2

class Solution(object):
    def canPlaceFlowers(self, A, N):
        for i, x in enumerate(A):
            if (not x and (i == 0 or A[i-1] == 0) 
                    and (i == len(A)-1 or A[i+1] == 0)):
                N -= 1
                A[i] = 1
        return N <= 0

접근 방법

• 어떤 조건에 꽃을 심을 수 있을지 하나의 조건문으로 정의하기

👉 꽃을 심을 수 있는 조건

1. flowerbed[i]=0 and i==0 and flowerbed[i+1]=0
2. flowerbed[i]=0 and flowerbed[i+1]=0 and flowerbed[i-1]=0
3. flowerbed[i]=0 and i==flowerbed[len(flowerbed)-1] and flowerbed[i-1]=0

위 세 가지 조건으로 하나의 if문으로 작성하면 된다.
if (not x and (i==0 or flowerbed[i-1]==0))) and (i=len(flowerbed)-1 or flowerbed[i+1]==0)

References

• https://leetcode.com/problems/can-place-flowers/
• https://leetcode.com/problems/can-place-flowers/discuss/1698406/Python3-SIMPLE-EXPLANATION-()
• https://leetcode.com/problems/can-place-flowers/discuss/103890/Python-Straightforward-with-Explanation