[Java] leetcode 605. Can Place Flowers

문제

Can Place Flowers - LeetCode

0 1 로 이루어진 꽃밭이 있는데, 꽃의 개수 n이 주어지면 심을 수 있는지 없는지 리턴하는 문제

 

풀이

이 풀이는 0, 1 로 이루어진 배열을 보니 0의 개수를 카운팅하면 풀수있을까? 에서 출발한다.

 

풀이 알고리즘은 다음과 같다.

1.    숫자 1 사이의 0의 개수 n 을 카운팅
2.    선형 탐색을 하여 숫자 1일때 (n-1)/2 를 answer 에 누적합 후 n = 0 초기화
3. 숫자 0 으로 시작하거나 끝나면 n +=1
4. count + (zeroCnt-1) / 2 >= n  을 리턴한다. 

단순히 1 과 1 사이의 0 의 개수를 카운팅한다. ( 예외는 뒤에 설명 )  

0의 개수	형태	1이 들어갈수 있는 max값
0	1 1	0
1	1 0 1	0
2	1 0 0 1	0
3	1 0 0 0 1	1
4	1 0 0 0 0 1	1
5	1 0 0 0 0 0 1	2
6	1 0 0 0 0 0 0 1	2
7	1 0 0 0 0 0 0 0 1	3
8	1 0 0 0 0 0 0 0 0 1	3

위의 표를 보면 1이 들어갈수 있는 max값이 규칙을 띄는 것을 볼수 있다.

여기서 알고리즘 2를 연역적 도출하였다. 

 

양 끝이 0 으로 이루어진 예외처리는 알고리즘 3, 4 의 방법으로 예외처리하였다. 

 

코드

자바

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if(flowerbed[0] ==0 && flowerbed.length ==1 )return true;
        int count= 0;
        int zeroCnt = 0;
        for(int i = 0 ;i < flowerbed.length ;i++){
            //count zero between 1
            if(flowerbed[i] == 0){
                if(i == 0 || i == flowerbed.length-1)//put 1 only if each side.
                    zeroCnt++;
                zeroCnt++;
            }else{
                count += (zeroCnt-1)/2;
                zeroCnt = 0;
            }
        }
        return count + (zeroCnt-1)/2 >= n;
    }
}