[Leetcode] 605. Can Place Flowers (C++ 풀이)

 

비어있는 상태 0 또는 꽃이 있는 상태 1인 형태의 flowerbed가 주어진다. 꽃은 절대 인접한 곳이 심겨있지 않다. 이 때, 얼마나 많은 꽃을 새로 인접하지 않은 채로 심을 수 있는지, 인자로 들어온 n 이상 심을 수 있으면 true 아니면 false를 반환하는 문제이다. 모든 i번째 요소를 탐색하며 앞뒤(i-1과 i+1) 영역을 탐색하면 되는 문제이다.

 

 

이 문제에서 신경써야 할 포인트는 flowerbed가 1일 수 있다는 점과 맨 앞과 맨 뒤의 요소를 어떻게 간결하게 처리할 것인가?이다. 맨 앞이거나 맨 뒤의 경우, 앞이나 뒤의 요소가 존재하지 않는다. 이때, index가 존재하지 않는 곳은 사실상 empty 상태인거나 마찬가지이므로 이를 0으로 처리해주면, 복잡한 조건식을 세울 필요 없이 문제를 풀 수 있다.

 

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int cnt = 0;

        for (int i=0; i < flowerbed.size(); i++){
            int left = (i==0) ? 0 : flowerbed[i-1];
            int right = (i==flowerbed.size()-1) ? 0 : flowerbed[i+1];

            if ((flowerbed[i] == 0) && (left == 0 && right == 0)){
                cnt += 1;
                flowerbed[i] = 1;
            }
        }

        if (cnt >= n)
            return true;
        else
            return false;
    }
};

 

left와 right를 구할 때, 삼항연산자를 이용해서 index out of range이면, 0으로 강제 할당하는 식으로 해당 조건을 해결할 수 있다. 총 카운트한 cnt 값이 주어진 n보다 같거나 크면 true, 아니면 false를 반환한다.