[Algorithm] LeetCode_605. Can Place Flowers (JAVA)

📝문제

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

💡풀이

 

문제 유형

구현, 그리디

 

걸린 시간

20분

 

시간 복잡도

O(N)

 

풀이 방법 도출

1. 맨 앞에서부터 양 옆으로 비어있는지 확인하고 비어있으면 카운트를 센다.
2. 현재보다 왼쪽을 prev로 두고 맨앞쪽일 땐 -1로 계산된다.
3. 왼쪽이 0이거나 -1이면서 오른쪽이 0이면서 현재도 0이면 현재 자리에 꽃이 들어올 수 있다.
4. 맨 마지막 값은 반복문을 나와 따로 계산해주었다.

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        //0:비어있음,1:꽃
        int prev = -1;
        int count = 0;
        for(int i = 0; i < flowerbed.length-1; i++){
            if((prev == 0 || prev == -1) && flowerbed[i+1] == 0 && flowerbed[i] == 0){
                flowerbed[i] = 1;
                count++;
            }
            prev = flowerbed[i];
        }

        if((prev == -1 || prev == 0) && flowerbed[flowerbed.length-1] == 0){
            count++;
        }

        return count >= n ? true : false;
    }
}

 

🤔Review

리트코드가 문제가 영어고, 출력값을 확인 못해보는 게 좀 아쉽지만 문제 퀄은 좋은 거 같다. 틀렸을 때 반례 테스트 케이스를 제공해줘서 편하다 ㅎㅎ