[LeetCode][Kotlin] 605. Can Place Flowers

605. Can Place Flowers

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

 

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

당신은 일부 플롯이 심어지고 일부는 심어지지 않은 긴 화단이 있습니다. 그러나 인접한 구획에는 꽃을 심을 수 없습니다. 

0과 1이 포함된 정수 배열 화단(0은 비어 있음을 의미하고 1은 비어 있지 않음을 의미)과 정수 n이 주어지면 인접 꽃 없음 규칙을 위반하지 않고 n개의 새 꽃을 화단에 심을 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

 

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1

Output: true

 

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2

Output: false

 

Constraints:

• 1 <= flowerbed.length <= 2 * 10^4
• flowerbed[i] is 0 or 1.
• There are no two adjacent flowers in flowerbed.
• 0 <= n <= flowerbed.length

---

코드 1

• 비어있는 플롯 양 옆에 꽃이 없다면 꽃을 심을 수 있다.
• 처음 플롯은 양 옆이 아닌 오른쪽에 꽃이 있는지 검사하면 된다.
• 마지막 플롯은 양 옆이 아닌 왼쪽에 꽃이 있는지 검사하면 된다.

class Solution {
    fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
        var answer = 0

        for (i in flowerbed.indices) {
            if (flowerbed[i] == 0) {
                val prev = if (i == 0) 0 else flowerbed[i - 1]
                val next = if (i == flowerbed.lastIndex) 0 else flowerbed[i + 1]
                if (prev == 0 && next == 0) {
                    answer++
                    flowerbed[i] = 1
                }
                if (answer == n) return true
            }
        }

        return answer >= n
    }
}

 

코드 2

• 코드 1 번과 방법은 동일하지만 문제가 되는 처음과 끝을 나머지와 맞추기 위해 양 옆에 [0] 을 추가한다.

class Solution {
    fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
        var answer = n
        val arr = intArrayOf(0) + flowerbed + intArrayOf(0)

        for (i in 1 until arr.lastIndex) {
            if (arr[i] == 0) {
                if (arr[i - 1] == 0 && arr[i + 1] == 0) {
                    arr[i] = 1
                    answer--
                }
            }
        }

        return answer <= 0
    }
}

 

코드 3 (어려움)

규칙을 정하기 위해 의식의 흐름대로 답을 도출해보았다.

• Example 1 과 Example 2 는 flowerbed = [1, 0, 0, 0, 1] 가 같고 n = 1, 2 이 다른 경우이다.

판단 1 : flowerbed 가 다른 경우가 필요해 보인다.

• Example 3 : flowerbed = [1, 0, 0, 0, 0], n = 2, true
• Example 4 : flowerbed = [0, 0, 0, 0, 1], n = 2, true
• Example 5 : flowerbed = [0, 0, 0, 0, 0], n = 3, true

판단 2 : 화단에 새 꽃을 심을 수 있는 개수를 파악해 보자.

• 판별 1 : Example 1, 2 - (3 + 1) / 2 = 2 (X) vs (4 + 1) / 2 (O) - Example 3, 4
  • Example 1, 2 의 심을 수 있는 개수를 맞추기 위해 필요한 조건을 설정하기에는 복잡해 보인다.
• 판별 2 : Example 1, 2 - (3 - 1) / 2 = 1 (O) vs (4 - 1) / 2 (X) - Example 3, 4

판단 3 : Example 3, 4, 5 의 심을 수 있는 개수를 맞추기 위해 다른 조건이 필요하다.

• 조건 1 - 맨 앞에 꽃이 심어져 있는 경우 - Example 1, 2, 3 vs Example 4, 5
  • var empty = if (flowerbed[0] == 1) 0 else 1
• 조건 2 - 맨 뒤에 꽃이 심어져 있는 경우 - Example 1, 2, 4 vs Example 3, 5
  • answer -= empty / 2

class Solution {
    fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
        var answer = n
        var empty = if (flowerbed[0] == 1) 0 else 1

        for (f in flowerbed) {
            if (f == 1) {
                answer -= (empty - 1) / 2
                empty = 0
            } else {
                empty += 1
            }
        }

        answer -= empty / 2
        return answer <= 0
    }
}