[leetcode] 605. Can Place Flowers

605. Can Place Flowers

문제

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

긴 화단에 중간 중간 식물이 심어져 있다. 식물은 바로 붙어서 자랄 수 없어 적어도 한 칸씩 띄워서 자라야 한다.

flowerbed라는 integer array는 0과 1로 구성되어 있으며, 0은 비어있음을 의미하고 1은 식물이 심어져 있음을 의미한다. n 값은 새로 심고자 하는 식물의 수이고, n개를 심을 수 있을 경우 true이고 심을 수 없을 경우 false를 반환한다.

풀이

답안1의 경우는 discuss를 보지 않고 처음 풀었을 때 나온 답안이라 좀 코드 자체가 복잡해 보인다. 답안1은 flowerbed를 0번째 인덱스부터 반복문을 돌 때, i번째의 위치가 맨 처음인지, 맨 마지막인지, 중간인지 나누어 풀었다.

• 만약 i가 0이라면, (i+1)번째가 0이거나 flowerbed.size()가 1일 때 1개를 심을 수 있다.
• i가 flowerbed.size() - 1이라면, (i-1)번째가 0일 때 1개를 심을 수 있다.
• i가 맨 처음도, 맨 마지막도 아니라면 (i-1)번째와 (i+1)번째 모두가 0일 때 1개를 심을 수 있다.

답안2는 답안1이 마음에 들지 않아 discuss를 보면서 다른 사람의 코드를 이해해 본 답안이다. 답안2를 보면, i문을 각각 2가지 경우로 나눠서 한 것을 알 수 있다.

• i가 0이거나, flowerbed[i-1] == 0
• i가 flowerbed.size() - 1이거나, flowerbed[i+1] == 0

즉, 답안1에서 3가지로 나눈 것을 if문 속에 ||로 표현하여 한 번에 녹인 것이라고 할 수 있다.

신기한 것은, 답안1과 답안2의 runtime 시간은 동일하다는 것이고.. 메모리는 오히려 답안2가 더 쓴다는 것이다(코드가 더러운지, 깔끔한지의 차이..).

답안1

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        for(int i = 0; i < flowerbed.size(); i ++) {
            if(n <= 0) break;
            if(flowerbed[i] == 1) continue;
            
            if(i == 0) {
                if(i + 1 < flowerbed.size() && flowerbed[i+1] == 0) {
                    n--;
                    flowerbed[i] = 1;
                }
                else if(i == flowerbed.size() - 1) {
                    n--;
                    flowerbed[i] = 1;
                }
            }
            else if(i == flowerbed.size() - 1) {
                if(i - 1 >= 0 && flowerbed[i-1] == 0) {
                    n--;
                    flowerbed[i] = 1;
                }
            }
            else {
                if(i - 1 >= 0 && i + 1 < flowerbed.size() && flowerbed[i-1] == 0 && flowerbed[i+1] == 0) {
                    n--;
                    flowerbed[i] = 1;
                }
            }
        }
        if(n <= 0) return true;
        else return false;
    }
};

답안2

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        for(int i = 0; i < flowerbed.size(); i ++) {
            if(n <= 0) break;
            if(flowerbed[i] == 1) continue;
            
            if((i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.size() - 1 || flowerbed[i+1] == 0)) {
                n--;
                flowerbed[i] = 1;
            }
        }
        if(n <= 0) return true;
        else return false;
    }
};