리트코드 - 605. Can Place Flowers

https://leetcode.com/problems/can-place-flowers/description/

Can Place Flowers - LeetCode

1. 빈 plot을 찾아 꽃을 심을 수 있는지 확인한다. 이를 위해 현재 plot이 비어 있는지, 그리고 이전과 다음 plot도 비어 있는지 확인한다.
2. 꽃을 심을 수 있는 곳을 찾으면 n을 감소시키고, n이 0이 되면 더 이상 확인할 필요가 없으므로 반복을 종료한다.
3. 리스트의 시작과 끝에서는 이전 또는 다음 플롯이 없으므로 별도로 처리할 수 있도록 한다.

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count = 0
        flowerbed = [0] + flowerbed + [0]  # 경계 조건을 처리하기 위해 양쪽에 0 추가 
        for i in range(1, len(flowerbed) - 1): # O(n)
            if flowerbed[i-1] == 0 and flowerbed[i] == 0 and flowerbed[i+1] == 0: # O(1)
                flowerbed[i] = 1 # O(1)
                count += 1
            if count >= n:
                return True
        return count >= n

 

flowerbed 리스트 양쪽에 빈 플롯을 추가함으로써 경계 조건을 쉽게 처리하고, 연속된 세 개의 빈 플롯이 있을 경우 중간 플롯에 꽃을 심는다.

시간 복잡도

시간 복잡도는 O(n)이다. 여기서 n은 flowerbed 리스트의 길이다.

공간 복잡도

공간 복잡도는 O(n)이다. 입력 리스트의 크기에 비례하는 공간을 할당한다.