[LeetCode] 605. Can Place Flowers

- Problem

605. Can Place Flowers

0과 1을 원소로 갖는 배열 flowerbed가 주어지고, 심어야 하는 flower의 갯수인n이 주어진다.

0을 빈 공간을 나타내고, 1은 꽃이 심어진 공간을 나타낸다.
주어진 꽃을 빈 공간에 모두 심을 수 있는지 판별하는 문제이다. 이 때, 인접한 구역에는 꽃을 심을 수 없다.

주어진 조건에서 최선의 선택을 해나가며 결과를 도출해내는 greedy 방식으로 접근해볼 수 있다.

- 내 풀이

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        N = len(flowerbed)

        if N == 1:
            if (flowerbed[0] == 0 and (n == 1 or n == 0)) or (flowerbed[0] == 1 and n == 0):
                return True
            return False

        for i in range(N):
            if flowerbed[i] == 0 and n > 0:
                if i == 0:
                    if flowerbed[i+1] == 0 and n:
                        flowerbed[i] = 1
                        n -= 1
                
                elif i == N - 1:
                    if flowerbed[i-1] == 0 and n:
                        flowerbed[i] = 1
                        n -= 1
                    
                else:
                    if flowerbed[i-1] == 0 and flowerbed[i+1] == 0 and n:
                        flowerbed[i] = 1
                        n -= 1
        
        return n == 0

풀이 방법은 쉽게 떠올려 볼 수 있으나 코드가 더럽다.

Refactoring Code

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        if n == 0:
            return True

        N = len(flowerbed)

        for i in range(N):
            if flowerbed[i] == 0:
                if (i == 0 or flowerbed[i-1] == 0) and (i == N - 1 or flowerbed[i+1] == 0):
                    flowerbed[i] = 1
                    n -= 1
    
            if n == 0:
                return True

        return False

- 결과

• 시간 복잡도: O(N) (N: flowerbed의 길이)
• 공간 복잡도: O(1)