[Python] LeetCode - 605. Can Place Flowers

LeetCode 605번 Can Place Flowers 문제는 일렬로 나열된 화분에 꽃들이 서로 인접하지 않게 심는 문제다. 난이도는 Easy이며 Greedy하게 해결할 수 있다.

 

리트코드 605번 Can Place Flowers 문제 정보

알고리즘 분류

- Greedy

난이도

- Easy

 

문제 요약

• 일렬로 된 화분이 있고, 꽃은 다른 꽃과 인접해서 심을 수 없다.
• 0: 빈 화분, 1: 꽃이 심어진 화분
• 화분 리스트와 새로 심어야 할 꽃의 개수가 주어질 때, 모든 꽃을 심을 수 있는지를 구하라.

 

문제 풀이 과정

• 앞에서부터 한칸씩 탐색하면서 심을 수 있으면 심고, n개의 꽃을 모두 심으면 True 아니면 False를 반환한다.

코드

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        for pos in range(len(flowerbed)):
            left, right = pos - 1, pos + 1
            if flowerbed[pos] == 0 and (left < 0 or flowerbed[left] == 0) and (right >= len(flowerbed) or flowerbed[right] == 0):
                flowerbed[pos] = 1
                n -= 1

            if n <= 0:
                return True
        return False

• 시간복잡도: O(1)
• 공간복잡도: 추가적인 공간 사용 X - O(1)