LeetCode 문제 풀이: 605. Can Place Flowers

🚀 문제: 605. Can Place Flowers

• 플랫폼: LeetCode

• 번호: 605

• 제목: Can Place Flowers

• 링크: https://leetcode.com/problems/can-place-flowers/

• 난이도: Easy

📝 문제 설명

정수 배열 flowerbed가 주어집니다. 이 배열에는 0과 1이 들어있는데, 1은 꽃이 이미 심어져 있는 칸을 의미하고 0은 비어있는 칸을 의미합니다. 또한, 정수 n이 주어집니다.

꽃은 인접한 두 칸에 동시에 심을 수 없습니다. 즉, 어떤 칸에 꽃을 심으면 그 바로 왼쪽 칸과 바로 오른쪽 칸에는 꽃을 심을 수 없습니다.

flowerbed에 n개의 새로운 꽃을 심을 수 있으면 true를, 없으면 false를 반환하세요. (배열의 경계를 넘어서는 것은 고려하지 않습니다. 즉, flowerbed[0]의 왼쪽이나 flowerbed[length-1]의 오른쪽에는 아무것도 없다고 가정합니다.)

예시 1:

• 입력: flowerbed = [1,0,0,0,1], n = 1

• 출력: true

• 설명: 가운데 0에 꽃 하나를 심을 수 있습니다.

예시 2:

• 입력: flowerbed = [1,0,0,0,1], n = 2

• 출력: false

• 설명: 하나의 꽃만 심을 수 있으므로 두 개는 불가능합니다.

🤔 풀이 아이디어: 비어있는 공간을 찾아 꽃 심기

제가 사용한 풀이 아이디어는 flowerbed를 문자열로 변환한 후, 1(이미 꽃이 심어진 곳)을 기준으로 나누어(split) 비어있는 공간(0들의 연속)을 찾는 것입니다. 그리고 각 비어있는 공간의 특성(맨 앞인지, 맨 뒤인지, 중간인지)에 따라 몇 개의 꽃을 심을 수 있는지 계산합니다.

1. 특별 케이스: 꽃밭에 꽃이 하나도 없는 경우 (flowerbed.count(1) == 0)

   • 만약 flowerbed에 1이 하나도 없다면, 모든 칸이 비어있습니다.

   • 이 경우, 심을 수 있는 꽃의 개수는 (배열의 길이 + 1) // 2가 됩니다. (예: [0,0,0] (길이 3) -> (3+1)//2 = 2개)

   • 이 값이 n보다 크거나 같으면 True를 반환합니다.

2. 일반 케이스: 꽃밭에 꽃이 하나 이상 있는 경우

   • flowerbed 배열을 문자열로 변환합니다. (예: [0,0,1,0,1] -> "00101")

   • 이 문자열을 "1"을 기준으로 분리하여 연속된 "0" 문자열들의 리스트를 얻습니다. (예: "00101" -> ["00", "0", ""])

   • flowerbed의 시작과 끝이 0인지 아닌지에 따라 4가지 경우로 나누어 처리합니다.

     • 시작은 0, 끝은 0이 아님 (예: [0,0,1,0,1]):

       • 맨 앞의 연속된 0들(parts[0])에는 len(parts[0]) // 2개의 꽃을 심을 수 있습니다.

       • 나머지 중간의 연속된 0들(parts[1:]의 빈 문자열이 아닌 요소)에는 (len(w) - 1) // 2개의 꽃을 심을 수 있습니다.

     • 시작은 0이 아님, 끝은 0 (예: [1,0,1,0,0]):

       • 맨 뒤의 연속된 0들(parts[-1])에는 len(parts[-1]) // 2개의 꽃을 심을 수 있습니다.

       • 나머지 중간의 연속된 0들(parts[:-1]의 빈 문자열이 아닌 요소)에는 (len(w) - 1) // 2개의 꽃을 심을 수 있습니다.

     • 시작과 끝 모두 0 (예: [0,0,1,0,0]):

       • 맨 앞(parts[0])과 맨 뒤(parts[-1])의 연속된 0들에는 각각 길이 // 2개의 꽃을 심을 수 있습니다.

       • 그 사이의 연속된 0들(parts[1:-1]의 빈 문자열이 아닌 요소)에는 (len(w) - 1) // 2개의 꽃을 심을 수 있습니다.

     • 시작과 끝 모두 0이 아님 (즉, 양 끝이 1이거나 단일 1 등) (예: [1,0,0,1]):

       • 모든 연속된 0들(parts의 빈 문자열이 아닌 요소)은 1과 1 사이의 공간이므로, (len(w) - 1) // 2개의 꽃을 심을 수 있습니다.

3. 최종 확인:

   • 위에서 계산된 총 심을 수 있는 꽃의 개수(place)를 구합니다.

   • place가 n보다 크거나 같으면 True를, 아니면 False를 반환합니다.

이 아이디어의 핵심은 "1이 없는 경우"라는 엣지 케이스를 먼저 처리하고, 그 외의 경우에는 배열의 양 끝 상태에 따라 split된 조각들을 다르게 해석하여 계산하는 것입니다.

💻 코드 (Python)

제가 직접 작성한 코드입니다.

Python
from typing import List

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        place = 0
        # 1. flowerbed에 '1'이 하나도 없는 경우 (가장 먼저 처리하는 엣지 케이스)
        if flowerbed.count(1) == 0:
            # 모든 칸이 0이므로, (길이+1)//2 만큼 심을 수 있음
            if (len(flowerbed)+1) // 2 >= n:
                return True
            else :
                return False
        # 아래는 flowerbed에 '1'이 하나 이상 있는 경우들입니다.
        # flowerbed의 시작과 끝이 0인지 여부에 따라 4가지 경우로 나눕니다.
        
        # 2-1. 시작은 0, 마지막은 0이 아닌 경우 (예: [0,0,1,0,1])
        elif ...