[Leetcode]605. Can Place Flowers

1. Problem : 

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

 

2. Solution1 : 

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        flowerbed.insert(0,0)
        flowerbed.append(0) 
        count = 0 
        i = 1 
        while i < len(flowerbed)-1 and n > 0:
            if flowerbed[i-1] == 0 and flowerbed[i+1] == 0 and flowerbed[i] == 0:
                count += 1 
                i += 2 
                n -= 1 
            elif flowerbed[i+1] == 1:
                i += 3 
            else:
                i +=2 
        if n <= 0:
            return True 
        return False

이 풀이 같은 경우는 0이라는 친구를 flowerbed 양끝에 더해서 문제를 푼다. 따라서,  i = 1부터 시작하고, 끝은 i == len(flowerbed)-1보다 작을 때 끝이 난다. 

이 문제의 핵심은 조건에 따라 i 값을 얼마나 변경시키느냐이다. 조건은 i-1, i, i+1 이 i의 양옆과 i가 0이라면 i += 2를 수행하고, i의 오른쪽이 1이라면 i +=3을 한다. 그 외의 경우라면 i += 2를 한다. 이렇게 하면 불필요한 계산을 없앨 수 있다. 

또한 while문에서 n > 0이라는 조건을 달아주어, 조건을 만족하면 loop를 끝나게 했다. 따라서, 불필요한 계산을 더 줄일 수도 있다. (상황에 따라) 

 

3. Solution2 : 

class Solution:
    def canPlaceFlowers(flowerbed: List[int], n: int) -> bool:
        id1, id2 = 0, 0
        l = len(flowerbed)
        id3 = 1 if l > 1 else 0 

        while id2 < l and n > 0:
            if flowerbed[id1] == 0 and flowerbed[id2] == 0 and flowerbed[id3] == 0:
                n -= 1
                flowerbed[id2] = 1
                id2 += 2
            else: 
                id2 += 1
            id1 = id2 - 1
            if id2 + 1 < l: id3 = id2 + 1 

        return n == 0

 이 풀이는 다른 사람의 풀이다. 이 풀이와 내 풀이의 다른 점은 0을 따로 양끝에 추가하지 않았다는 점이다. 또한, if 조건문을 만족할 때는 나의 풀이와 똑같지만, else: 일 때는 id2 += 1이라는 점이 다르다. 나는 이 풀이가 불필요한 계산을 더 할 수도 있다고 생각한다. 하지만, 실행속도는 매우 빨랐다. 

 

3. Solution 3: 

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        if n == 0:
            return True
        for i in range(len(flowerbed)):
            if flowerbed[i] == 0 and (i == 0 or flowerbed[i-1] == 0) and (i == len(flowerbed)-1 or flowerbed[i+1] == 0):
                flowerbed[i] = 1
                n -= 1
                if n == 0:
                    return True
        return False

이 풀이는 사실 for loop를 다 거치는 방식이다. 따라서, 불필요한 계산을 많이 하게 된다. 그럼에도 불구하고 내가 이 solution을 가져온 이유는, if 문의 case분류에서 발견한 특이점이 있어서이다. 

 

if 문을 보면, (i == 0 or flowerbed [i-1] flowerbed [i-1] == 0)이 있다. 이때, i == 0이라면 flowerbed [i-1]은 오류가 난다.(index out of range). 하지만 , 실제로 돌려보면, 오류가 나지 않는다. 그 이유는 조건 1 or 조건 2가 있을 때, 조건 1이 옳다면 조건 2는 검사하지 않아서 그런 것 같다. 따라서 , 저렇게 작성하는 하나의 trick도 배우게 되었다.