[LeetCode] 605. Can Place Flowers

1. 문제 이해

화단 리스트에는 일부 자리가 이미 꽃으로 채워져 있다.

인접한 곳에 꽃을 심을 수 없다는 규칙이 있다.

0은 비어 있는 자리, 1은 이미 꽃이 심어진 자리를 뜻한다.

n개의 꽃을 새로 심을 수 있는지 확인한다.

가능하다면 True를 리턴하고 불가능하다면 False를 리턴한다.

 

 

2. 풀이 과정

빈 자리(0)를 찾기 위해 flowerbed 리스트를 순회한다.

현재 위치가 0이고, 왼쪽과 오른쪽이 비어 있으면 그 자리에 꽃을 심는다.

flowerbed 리스트에서 해당 자리를 1로 바꾼다.

꽃을 심을 때마다 cnt를 증가시킨다. cnt가 n과 같거나 많아지면 True를 반환한다.

끝까지 순회했는데도 n개를 다 심지 못했다면 False를 반환한다.

 

 

3. 전체 코드

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

 

 

4. 생각할 점

- or을 사용하여 리스트의 경계(left < 0, right >= len(flowerbed))를 처리한다.

- 이렇게 그리디하게 꽃을 심는 게 최선의 결과를 보장할까?(꽃을 심을 수 있는 최대 개수를 구할 수 있을까?)

 

 

5. 출처

- https://leetcode.com/problems/can-place-flowers/?envType=study-plan-v2&envId=leetcode-75