LeetCode 605. Can Place Flowers

접근 오류

❗️처음에 생각한 방향

단순하게 꽃을 하나 놓을 수 있을 때마다 n만 감소하는 방향으로 처음에 생각

이렇게 할 시 문제점은 꽃을 넣은 것을 배열에 표시해두지 않기 때문에 이 후 꽃을 놓을 수 있는 가능성이 훼손됨

따라서 꽃을 놓은 자리를 0에서 1로 바꾸고 계산하기 시작

 

⛔️ 처음 코드의 문제점: 발생하는 예외사항에 대한 처리 미흡

    - n과 flowerbedSize, 그리고 flowerbed[0], flowerbed[flowerbedSize-1]에 따라 따로 처리해야 되는 부분 존재하지만

     이를 간과하고 코드를 짜서 오류 발생

    - 이를 생각해서 코드를 짜려고 했지만 예외를 깔끔하게 정리하지 않아서 한 예외를 처리하면 다른 예외를 처리하지 못하는 부분 발생

    - n >= flowerbedSize/2 + 1 로 예외처리를 하려고 한 부분이 Error (길이와 상관없이 0 || 1 에 따라 예외 발생 경우의 수 많음)

bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n){

    if(n==0) return true;
    if(n==1 && flowerbedSize==1) {
        if(!flowerbed[0]) return true;
        else return false;
    }

    if(n >= flowerbedSize/2 + 1) return false;

    if(!flowerbed[0] && !flowerbed[1]) { flowerbed[0] = 1 ; n--;}
    if(!flowerbed[flowerbedSize-2] && !flowerbed[flowerbedSize-1]) { flowerbed[flowerbedSize-1] = 1; n--;}

    for(int i=2; i<flowerbedSize-1; i++){
        if(!flowerbed[i-1] && !flowerbed[i] && !flowerbed[i+1]) {
            flowerbed[i] = 1;
            n--;
        }
    }


    if(n <= 0) return true;
    else return false;
}

 

접근

✅ flowerbedSize가 커질 수록 for문을 많이 돌아야하므로 처음에 간단하게 처리할 수 있는 예외는 exception으로 따로 빼줌

    - n이 0이거나 1인 경우는 바로 처리 가능하므로 처리

 

✅ 맨 처음과 맨 끝 부분에 대한 예외 처리

    - 가장 많은 꽃을 놓을 때, 양 끝은 항상 놓는 것이 유리

    - 양 끝에 꽃을 놓을 수 있는 경우는 각각

    맨 앞: flowerbed[0], flowerbed[1] 이 모두 0일 때

    맨 뒤: flowerbed[flowerbedSize-1], flowerbed[flowerbedSize-2] 이 모두 0일 때

        > 위 조건을 만족하면 맨 앞 혹은 맨 끝에 꽃 두고(n--) 1로 바꾸기

 

✅ 예외 처리를 한 이유는, 맨 앞과 맨 뒤는 2개의 배열만 보는 데 반해 가운데에 있는 부부은 (0,0,0) 이렇게 3개의 배열을 봐야함

     - 따라서 for문의 범위도 최대 flowerbedSize-2로 둠

 

✅ 내 코드의 경우, 꽃을 놓을 수 있는 모든 경우에 n-- 를 하므로 최종적으로 n이 음수가 될 수 있음을 생각하고 마지막 조건문 짜기

    : 즉, 조건문은 n <= 0

 

 

구현

시간복잡도 : O(n)

bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n){

//exceptions
    if(n==0) return true;
    if(n==1 && flowerbedSize==1) {
        if(!flowerbed[0]) return true;
        else return false;
    }
    if(!flowerbed[0] && !flowerbed[1]) { flowerbed[0] = 1 ; n--;}
    if(!flowerbed[flowerbedSize-2] && !flowerbed[flowerbedSize-1]) { flowerbed[flowerbedSize-1] = 1; n--;}

//non exceptions
    for(int i=1; i<flowerbedSize-2; i++){
        if(!flowerbed[i-1] && !flowerbed[i] && !flowerbed[i+1]) {
            flowerbed[i] = 1;
            n--;
        }
    }

    if(n <= 0) return true;
    else return false;
}

 

Take aways

✅ 일단 주어진 문제에 대해 예외처리할 사항이 있다면 해주기

     - 특히, 일반적인 처리와 다른 부분이 있다면 예외로 깔끔하게 빼서 복잡도 줄이기

 

✅ 기본적인 부분 : 배열의 제일 끝은 size-1 이라는 거 잊지말기

 

✅ 다른 요소에 종속적인 문제의 경우, 꼭 바뀐 내용(변수 등) 같이 코드화해서 업데이트 해주기

    - 이 문제의 경우, flowerbed[i] = 1 하는 것