23.03.20. 풀었던 문제들

Leetcode 605. Can Place Flowers

 간단한 simluation 문제.

• 앞에서부터 순회한다. [현재 위치(i)] 앞에는 1이 없어 설치 가능하다는 것을 전제로 한다.
• 위 전제를 맞춰주기 위한 indexing이 필요하다.
• 만약 arr[i] == 0이라면
  • i+1이 범위 밖이거나 arr[i+1]이 0이라면 설치할 수 있다.
  • 설치했다면 i부터 [0, 0, ?]인 상태이므로 i += 2를 한다.
  • 설치하지 못했다면 [0, 1, ?]인 상태이므로 i += 1을 한다.
• arr[i] == 1이라면
  • 문제 조건에 따라 arr[i+1]은 무조건 0이다. 단 i+1에도 설치하지 못한다. 따라서 i += 2를 한다.

// Runtime 10 ms Beats 97.73%
// Memory 20.3 MB Beats 76.11%

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int i = 0, len = flowerbed.size();
        while(1){
            if(i >= len || len <= 0) break;
            if(flowerbed[i] == 0){
                
                if(i+1 >= len || (i+1 < len && flowerbed[i+1] == 0)){
                    n--;
                    i += 2;
                }
                else i++;
            }
            else{
                i += 2;
            }
        }

        return n <= 0;
    }
};

 

 

조금 더 직관적인 풀이

 시간은 좀 더 걸리지만 좀 더 직관적인 풀이도 있다.

• 현재 위치(i)의 arr[i]가 0일 때 left, right를 확인한다.
  • left는 i-1이 범위를 벗어나거나 arr[i-1] == 0일 때 true
  • right는 i+1이 범위를 벗어나거나 arr[i+1] == 0일 때 true
  • left && right일 때 해당 위치에 설치할 수 있다. arr[i] == 1이 되므로 i+1에는 설치할 수 없다. 따라서 i+2로 넘어간다.

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {


        int len = flowerbed.size();
        for(int i = 0; i<len; i++){
            if(flowerbed[i] == 0){
                int leftzero = (i-1 < 0 || flowerbed[i-1] == 0);
                int rightzero = (i+1 >= len || flowerbed[i+1] == 0);
                if(leftzero && rightzero){
                    flowerbed[i] = 1;
                    i++;
                    n--;
                }
            }
        }

        return n <= 0;
    }
};

 

 

좀 더 간단하게

 아래 코드는 솔루션 보면서 찾은 건데, 아주 간단하게 작성할 수 있다. arr의 제일 앞, 제일 뒤에 0을 추가하고 1부터 size()-1까지 검사하면 범위 바깥으로 나가는 예외처리를 할 필요가 없다. 실제로 코드도 아주 간단하다!

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        flowerbed.insert(flowerbed.begin(),0);
        flowerbed.push_back(0);
        for(int i = 1; i < flowerbed.size()-1; ++i)
        {
            if(flowerbed[i-1] + flowerbed[i] + flowerbed[i+1] == 0)
            {
                --n;
                ++i;
            }
                
        }
        return n <=0;
    }
};

 

 

 

시간복잡도

 앞에서부터 순회하므로 O(n)

 

공간복잡도

 추가공간을 사용하지 않으므로 O(1)이다.