[알고리즘] LeetCode_#605

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.

✨ Example

🚨 Constraints

▶︎ 풀이

• 현재 인덱스가 i이고 값이 0일때, 인접한 인덱스 i-1(left), i+1(right)의 값이 둘 다 0이면 심을 수 있음
  → 이 때, i가 0(left가 없음), length-1(right 가 없음)에 주의
• flowerbed[i]의 값을 1로 변경, 심을 때 count 증가
  → count : 심을 수 있는 꽃의 수
• count 가 n보다 크거나 같으면 n개의 꽃을 모두 심을 수 있음

⏰ 제한시간 초과하여 답안 코드 및 풀이 확인

🚨 제약조건(Contraints) 확인

▶︎ 기존코드

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
       int count = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0) {
                boolean emptyLeftPlot = (i == 0) || (flowerbed[i - 1] == 0);
                boolean emptyRightPlot = (i == flowerbed.length - 1) || (flowerbed[i + 1] == 0);
                if (emptyLeftPlot && emptyRightPlot) {
                    flowerbed[i] = 1;
                    count++;
                }
            }
        }
        return count >= n;
    }
}

▶︎ 개선사항

✨ 실행 속도 최적화

1. for문 수정
   증감식 : flowerbed[i]의 값이 1이면 다음 칸은 심을 수 없음 → i+2(그 다음 칸)을 확인
2. 제약조건 간략화
   flowerbed[i]의 값이 0이고 flowerbed[i+1]이 1이면 flowerbed[i+2]에 심을 수 없음
   ⇒ i++ 다음 증감식(i+=2) : i+3번째 칸부터 다시 확인
3. 변수 선언
   별도의 count 변수를 선언하지 않고 n 활용

▶︎ 수정코드

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {		
         for(int i=0;i<flowerbed.length;i=i+2){
            if(flowerbed[i]==0){
                if(i==flowerbed.length-1 || flowerbed[i] == flowerbed[i+1] ){
                    n--;
                } else{
                    i++;
                }
            }
        }
        return n<=0;
    }
}