[LeetCode] Can Place Flowers

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

 

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.

 

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1

Output: true

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2

Output: false

 

Constraints:

• 1 <= flowerbed.length <= 2 * 104
• flowerbed[i] is 0 or 1.
• There are no two adjacent flowers in flowerbed.
• 0 <= n <= flowerbed.length

 

꽃이 심어진 곳은 1, 심어지지 않은 곳은 0으로 표시한 int[]가 있다.

여기에 양 옆 칸이 빈 곳에만 새로운 꽃을 심을 수 있다고 했을 때,

주어진 수 n개의 꽃을 심을 수 있는지 체크해서 리턴하는 문제다.

 

1과 0으로만 이루어진 배열이다보니 비트연산자로 어떻게 처리할 수 없을까 했는데.. 그건 무리일 것 같았다.

그래서 우선 꽃을 심을 수 있는 조건을 나열했다.

 

1) 1 사이에 0이 2n+1개 있는 경우, 꽃을 n개 심을 수 있음. (한 쪽에만 1이 있는 경우도 마찬가지)

2) 0만 있다면 2n개 있을 때 꽃을 n개, 2n+1개 있어도 n개 심을 수 있음.

3) ... 등등... 

 

이런 식으로 접근하니까 경우의 수가 너무 많아지고... 접근도 어려웠다. 그 모든 조건을 다 나열할 것도 아니고? 그게 의미가 있냐구?

그래서 연속된 2개의 빈칸이 있고, 그 다음 칸이 1이 아니라면 심을 수 있는 칸이 1개 늘어난다고 가정하고 문제를 풀었다.

 

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    let emptyCnt = 0;
    let availableBed = 0;
    flowerbed.map((bed, i)=>{
        if (bed === 0){
            emptyCnt++;
        }
        if (emptyCnt === 2){
            flowerbed[i+1] !== 1 && availableBed++;
            emptyCnt = 0;
        }
    });

    return n <= availableBed;
};

 

하지만 그런 식으로 하면ㅋㅋㅋ [0,0,1,0,1] 인 경우에는 심을 수 있는 칸이 0으로 나왔다.

연속된 칸이 몇개인지뿐만이 아니라 앞 칸이 비어있는지도 확인을 해야했고, 그렇게 정리하다보니...

 

양 옆 칸이 비어 있으면 꽃을 심을 수 있다.

앞 칸 또는 뒤 칸이 없는 있는 경우에는 반대쪽이 빈 칸일 때 꽃을 심을 수 있다.

라고 단순하게 접근하면 되겠다는 것을 깨달았다.

 

근데 막상 또 코드로 구현하니 그렇게 단순하지 않았다ㅋㅋㅋㅋㅋ

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    let availableBed = 0;

    for(let i=0; i<flowerbed.length; i++){
        // 내가 0일때, 앞 뒤로 1이 없거나 앞 또는 뒤의 값이 없어야 한다.
        if (flowerbed[i] === 0){
            if(flowerbed[i+1] === 0 && flowerbed[i-1] === 0){
                availableBed++;
                flowerbed[i] = 1;
            }
            if(flowerbed[i-1] == undefined && flowerbed[i+1] === 0){
                availableBed++;
                flowerbed[i] = 1;
            }
            if(flowerbed[i-1] === 0 && flowerbed[i+1] == undefined){
                availableBed++;
                flowerbed[i] = 1;
            }
            if(flowerbed[i-1] === undefined && flowerbed[i+1] === undefined){
                availableBed++;
                flowerbed[i] = 1;
            }
        }
    }

    return n <= availableBed;
};

 

 

하지만 플라워베드의 배열이 1과 0으로 이루어져있다는 점을 활용하면...

아래와 같이 간단하게 요약할 수 있었다!!!

 

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    let availableBed = 0;

    for(let i=0; i<flowerbed.length; i++){
        // 내가 0일때, 앞 뒤로 1이 없거나 앞 또는 뒤의 값이 없어야 한다.
        if (!flowerbed[i] && !flowerbed[i+1] && !flowerbed[i-1]){
            availableBed++;
            flowerbed[i] = 1;
        }
    }

    return n <= availableBed;
};

 

난이도 Easy 문제는 풀고 나면 별 거 아닌데 아이디어를 내는 과정이 쉽지 않은 것 같다.