[LeetCode 75] Easy - 605. Can Place Flowers

 

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        new_flowerbed = [0] + flowerbed + [0]
        for i in range(1, len(new_flowerbed)-1): #  skip first & last
            if new_flowerbed[i] == 0 and new_flowerbed[i-1] == 0 and new_flowerbed[i+1] == 0:
                new_flowerbed[i] = 1
                n -= 1
                #if n == 0:
                #    return True
        return not (n>0) # 남은 꽃이 있으면 False 반환

605. Can Place Flowers

 

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.

 

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)에서 꽃을 심을 수 있는 위치를 찾아, nnn개의 꽃을 심을 수 있는지 판단하는 문제입니다. 심을 때 규칙은 다음과 같습니다:

1. 꽃은 서로 인접한 위치에 심을 수 없습니다.
2. 현재 위치가 비어 있더라도, 양 옆에 꽃이 없어야 꽃을 심을 수 있습니다.
3. 꽃을 심을 수 있는 자리를 확인한 뒤, nnn개의 꽃을 모두 심을 수 있으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        new_flowerbed = [0] + flowerbed + [0]
        for i in range(1, len(new_flowerbed)-1): #  skip first & last
            if new_flowerbed[i] == 0 and new_flowerbed[i-1] == 0 and new_flowerbed[i+1] == 0:
                new_flowerbed[i] = 1
                n -= 1
                if n == 0:
                    return True
        return not (n>0) # 남은 꽃이 있으면 False 반환

 

 

https://youtu.be/ZGxqqjljpUI?si=Z15-LbV_3SjAlVLw

 

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        new_flowerbed = [0] + flowerbed + [0]
        for i in range(1, len(new_flowerbed)-1): #  skip first & last
            if new_flowerbed[i] == 0 and new_flowerbed[i-1] == 0 and new_flowerbed[i+1] == 0:
                new_flowerbed[i] = 1
                n -= 1
                #if n == 0:
                #    return True
        return not (n>0) # 남은 꽃이 있으면 False 반환

 

GPT 코드 와의 차이

 

문제의 요구 조건 중 관련된 부분:

"Return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise."

 

이 문장에서 의미 추출:

1. If n new flowers can be planted:
   • 문제에서 nnn개의 꽃을 심는 데 성공했다면 True를 반환해야 합니다.
   • 즉, n개의 꽃을 모두 심었을 때(n == 0), 더 이상 검사할 필요가 없다는 의미를 내포합니다.
2. Without violating the rule:
   • n==0 이 되면 규칙을 위반하지 않은 상태에서 n 개의 꽃을 심었다는 조건을 만족하므로, 바로 True를 반환할 수 있습니다.

 

명시적이지 않은 이유

문제는 특정 구현 방식에 대해 지시하지 않으며, n==0n == 0n==0이라는 조건을 활용하는 최적화는 구현자의 재량에 맡깁니다. 따라서 문제의 문장에서 이 내용을 직접적으로 찾기 어렵지만, 위 문장에서 암시된 의미를 코드로 최적화한 결과라고 이해하면 됩니다.

 

따라서, GPT 코드가 아래 부분 로직으로 인해, for loof 를 적게 돌아서, 속도가 좀더 빠름

if n == 0:
	return True