(Leet Code JS)Can Place Flowers

https://leetcode.com/problems/can-place-flowers/

Can Place Flowers - LeetCode

그리디 알고리즘.

n개의 꽃을 flowerbed에 심어야 하는데, 근접한 위치에 꽃이 없어야 한다.

 

for문을 이용해 flowerbed를 순회.

만약 현재 n이 0이라면 모두 심었기 때문에 바로 true를 리턴한다.

그렇지 않고 n이 남아있다면 최대한 꽃을 심어본다.

 

맨 앞에서부터 꽃을 심으면 최대로 꽃을 심을 수 있기 때문에 0부터 인덱스를 시작했다.

만약 flowerbed[i]가 0이면 꽃을 심을 수 있는 후보군이다.

인접한 위치에 꽃이 없다면 꽃을 심을 수 있다.

 

i === 0 or i === flowerbed.length - 1, i > 0 ~ i < flowerbed.length에 따라 조건을 지정한다.

 

i === 0이면

현재 위치에서 오른쪽만 검사.

 

i === flowerbed.length -1 이면

현재 위치에서 왼쪽만 검사.

 

나머지는 양 옆을 검사한다.

 

검사할 인덱스를 인자로 주어 checkAdjacent()함수로 조건을 검사한다.

매개 변수로 받은 인덱스가 0이면 true, 1이면 false를 리턴하는 함수다.

 

위 조건이 true라면 꽃을 심고, i번째 인덱스를 1로 바꾼다.

 

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
    const checkAdjacent = (i) => flowerbed[i] ? false : true;
    
    for(let i = 0; i < flowerbed.length; i++){
        if(!n){
            return true;
        }
        
        if(!flowerbed[i]){
            if(i === 0){
                if(checkAdjacent(i + 1)){
                    n--;
                    flowerbed[i] = 1;
                }
            } else if(i === flowerbed.length - 1){
                if(checkAdjacent(i - 1)){
                    n--;
                    flowerbed[i] = 1;
                }
            } else{
                if(checkAdjacent(i - 1) && checkAdjacent(i + 1)){
                    n--;
                    flowerbed[i] = 1;
                }
            }
        }
    }
    
    return !n;
};