[그리디] 605. Can Place Flowers

문제 링크

 

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

 

문제 접근 방법

1) 점화식

일단 0의 갯수와 꽃을 심는 개수의 상관관계를 파악하기 위해 패턴을 분석해보니 0이 3개가 연속으로 있을 때 1개까지 심을 수 있고, 0이 5개일 때 2개, 7개일 때 3개... 이런 식으로 되는 것 같았다.

점화식을 세우고 이걸 활용하기로.

 

 

고민한 부분

후. 조건 처리를 생각하느라 골치 아팠다.

연속하는 애들을 어떻게 케이스를 나누어 처리할건지였는데,

일단 0이면 꽃을 심을 수 있는 공간이니 consecitive_zeros에다가 1을 더해주고,

그렇지 않은 경우(1인 경우)에는 consecitive_zeros가 일단 0으로 초기화가 되어야 함과 동시에 n 연산을 점화식으로 연산해주어서 n이 0이 되면 true인거고 아니면 false인거다.

 

 

 

주의사항

-엣지케이스 처리(for 루프 전후에도 꽃을 심을 공간(0)이 있는 경우)를 위해 그냥 처음부터 효율적으로 0을 앞뒤로 추가함

-루프 밖을 벗어나게 되면 0에 대한 연속적인 계산도 끝나므로, 루프 밖에서도 n에 대한 연산을 해주어야 한다는 것

 

코드

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

        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                consecutive_zeros += 1
            else:
                n -= (consecutive_zeros - 1) // 2
                if n <= 0:
                    return True
                consecutive_zeros = 0
        n -= (consecutive_zeros - 1) // 2
        return n <= 0

 

 

풀고 나서 (접근법, 사용되는 알고리즘 개념)

투포인터 기법으로도 풀 수 있다(이게 나은 듯 싶기도 하지만.. 그냥 자기가 편한거 따라서?)