문제 개요
길게 이어진 화단이 있다고 가정해 보겠습니다. 화단의 일부 구역에는 이미 꽃이 심어져 있고, 나머지 구역은 비어 있습니다. 여기에는 한 가지 중요한 규칙이 있습니다. 바로 인접한 구역에는 꽃을 심을 수 없다는 것입니다. 서로 붙어 있는 두 꽃은 물을 두고 경쟁하게 되어 결국 둘 다 시들어 버리기 때문입니다.
따라서 화단의 상태는 0과 1로 이루어진 배열로 주어집니다(0은 빈 구역, 1은 꽃이 심긴 구역). 여기에 숫자 n이 함께 주어질 때, 인접 금지 규칙을 어기지 않으면서 n개의 새 꽃을 심을 수 있는지 판별하는 것이 이 문제의 목표입니다.
예를 들어 입력이 flowerbed = [1,0,0,0,1], n = 1이라면, 가운데 빈 구역(인덱스 2)에 꽃을 심을 수 있으므로 출력은 True가 됩니다.
접근 방법
이 문제는 그리디(greedy) 방식으로 해결할 수 있습니다. 왼쪽부터 차례대로 각 구역을 확인하면서, 해당 구역과 양옆 구역이 모두 비어 있으면 즉시 꽃을 심는 것입니다. 이렇게 하면 항상 최대한 많은 꽃을 심을 수 있으므로, n개를 모두 심을 수 있는지 정확하게 판별할 수 있습니다.
알고리즘 단계
- 화단의 크기가 n보다 작으면 false를 반환합니다.
- 화단 크기가 1이고 flowerbed[0]이 0이며 n이 1이라면 true를 반환합니다.
- i를 0부터 화단 크기 - 1까지 순회하며 다음을 수행합니다.
- n > 0일 때,
- i가 0이고 flowerbed[i]와 flowerbed[1]이 모두 0이면 flowerbed[0]을 1로 바꾸고 n을 1 감소시킵니다.
- i가 마지막 인덱스이고 flowerbed[i]가 0이며 flowerbed[i-1]이 1이 아니라면 flowerbed[i]를 1로 바꾸고 n을 1 감소시킵니다.
- 그 외의 경우, flowerbed[i], flowerbed[i+1], flowerbed[i-1]이 모두 0이라면 flowerbed[i]를 1로 바꾸고 n을 1 감소시킵니다.
- n이 0이 되면 true를 반환합니다.
- n > 0일 때,
- 반복이 끝난 후에도 n이 0이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
if (flowerbed.size() < n)
return false;
if (flowerbed.size() == 1 && flowerbed[0] == 0 && n == 1)
return true;
for (int i = 0; i < flowerbed.size(); i++) {
if (n > 0) {
if (i == 0) {
if (flowerbed[i] == 0 && flowerbed[1] == 0) {
flowerbed[0] = 1;
n--;
}
}
else if (i == flowerbed.size() - 1) {
if (flowerbed[i] == 0 && flowerbed[i - 1] != 1) {
flowerbed[i] = 1;
n--;
}
}
else if (flowerbed[i] == 0 && flowerbed[i + 1] == 0 && flowerbed[i - 1] == 0) {
flowerbed[i] = 1;
n--;
}
}
if (n == 0) {
return true;
}
}
if (n == 0) {
return true;
}
return false;
}
};
main(){
Solution ob;
vector<int> v = {1,0,0,0,1};
cout << (ob.canPlaceFlowers(v, 1));
}
입력
{1,0,0,0,1}, 1출력
1
복잡도 분석
시간 복잡도는 O(N)입니다. 화단 배열을 한 번만 순회하면 충분하기 때문입니다. 공간 복잡도는 O(1)로, 입력 배열 자체를 수정하며 별도의 추가 메모리를 사용하지 않습니다.
참고로, 배열 양 끝에 0을 하나씩 추가한 뒤(패딩 처리) 경계 조건 없이 일관되게 검사하는 방법도 널리 사용되는 대안적인 접근 방식입니다. 이 경우 첫 구역과 마지막 구역을 특별 케이스로 분리하지 않아도 되어 코드가 더 간결해집니다.