[Array/String][Easy] 605. Can Place Flowers

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

Can Place Flowers - LeetCode

 

Q. 각 자리가 1일때 flow가 planted되어 있고, 0이면 그렇지 않다.
flower는 연속해서 plant할 수 없다.
이때, n의 flowers를 더 심으려고 한다면, 가능하지 여부를 반환하라.

 

Key : 

 이웃하지 않게 n을 감소시키면서 원하는 job을 n이 모두 소모될때 까지 진행시키면 된다. 

 이때, 처음과 마지막의 예외처리, 그리고 도중 원래 배열의 update가 원활하게 이루어진다면 해결. 

 대체로 TC가 O(N)이면 적당한 solution일 경우가 대다수 이다. 

 

bool canPlaceFlowers(vector<int>& flowerbed, int n)
{
    // 각 자리가 1일때 flow가 planted되어 있고, 0이면 그렇지 않다.
    // flower는 연속해서 plant할 수 없다.
    // 이때 n의 flowers를 더 심으려고 한다면, 가능하지 여부를 반환하라.
    //
    if (n == 0)	return true;
    if (flowerbed.size() == 1)
        return flowerbed[0]==0 && n==1;

    for (int k = 0; k < flowerbed.size(); ++k)
    {
        bool plant = false;
        if (k == 0)
        {
            if (flowerbed[k]==0 && flowerbed[k+1]==0)
                plant = true;
        }
        else if (k == flowerbed.size() - 1)
        {
            if (flowerbed[k] == 0 && flowerbed[k - 1] == 0)
                plant = true;
        }
        else
        {
            if (flowerbed[k - 1] == 0 && flowerbed[k] == 0 && flowerbed[k + 1] == 0)
                plant = true;
        }
        if (plant)
        {
            --n;
            flowerbed[k] = 1;
        }
        if (n <= 0)	return true;
    }
    return false;
}

 

TimeComplexity : O(N)

Comment : 단순하게 생각해야 쉽게 풀수 있는문제. 배열 easy급 난이도에 적절한 문제인 듯.