LeetCode [605]: Can Place Flowers

📌 LeetCode [605]: Can Place Flowers

🔗 문제 링크

---

문제 설명 📄

flowerbed라는 정수 배열과 정수 n이 주어집니다.
배열의 각 요소는 0(비어 있음) 또는 1(꽃 심어져 있음)을 나타냅니다.
꽃은 인접한 곳에 심을 수 없습니다.
n개의 꽃을 심을 수 있으면 True, 그렇지 않으면 False를 반환하세요.

---

문제 접근 방식 📋

1. 현재 위치에서 심을 수 있는지 판단:
   • 현재 위치가 0이고, 좌우 모두 0이라면 꽃을 심을 수 있습니다.
2. 조건 확인:
   • 꽃을 심으면 해당 위치를 1로 변경하고 n을 감소시킵니다.
   • 모든 꽃을 심으면 (n == 0) True를 반환합니다.
3. 최종 판단:
   • 반복문 종료 후에도 n이 남아 있으면 False를 반환합니다.

---

Solution 💻

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        def jud(index):
            left = index - 1
            right = index + 1

            if left < 0 and right < len(flowerbed):
                if flowerbed[right] == 0:
                    return True
            elif right > len(flowerbed) - 1 and left >= 0:
                if flowerbed[left] == 0:
                    return True
            elif left >= 0 and right < len(flowerbed):
                if flowerbed[right] == 0 and flowerbed[left] == 0:
                    return True
            else:
                return True
            return False

        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                if jud(i):
                    flowerbed[i] = 1
                    n -= 1
                if n == 0:
                    return True

        if n <= 0:
            return True

        return False

시간 복잡도 분석 ⏲️

• 반복문: 배열을 한 번 순회 (O(n)).
• 조건 확인: 각 위치에서 jud 함수 호출 (O(1)).
• 총 시간 복잡도: O(n).

공간 복잡도 분석 🗄️

• 추가 메모리 사용 없음.
• 총 공간 복잡도: O(1).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count = 0
        for i in range(len(flowerbed)):
            if flowerbed[i] == 0 and (i == 0 or flowerbed[i - 1] == 0) and (i == len(flowerbed) - 1 or flowerbed[i + 1] == 0):
                flowerbed[i] = 1
                count += 1
                if count >= n:
                    return True
        return count >= n

리팩토링 후 시간 복잡도 ⏲️

• 배열 순회: 배열을 한 번 순회 (O(n)).
• 총 시간 복잡도: O(n).

리팩토링 후 공간 복잡도 🗄️

• 추가 메모리 사용 없음.
• 총 공간 복잡도: O(1).

---