Can Place Flowers — `O(n)` 그리디 스캔으로 인접 금지 배치 판정
스터디·6분 읽기
인접한 화단에 꽃을 동시에 심을 수 없을 때 `n`송이 배치가 가능한지 판단하는 LeetCode 605번, 그리디 선택이 왜 최적인지와 배열 수정 없이 `O(n)`/`O(1)`로 푸는 방법을 정리합니다.
2개의 글
인접한 화단에 꽃을 동시에 심을 수 없을 때 `n`송이 배치가 가능한지 판단하는 LeetCode 605번, 그리디 선택이 왜 최적인지와 배열 수정 없이 `O(n)`/`O(1)`로 푸는 방법을 정리합니다.
삼중 반복 `O(n^3)`부터, `leftMin`/`rightMax` 두 배열을 쓰는 `O(n)`/`O(n)`, 그리고 변수 두 개로 `O(n)`/`O(1)`에 푸는 그리디까지, `first`/`second` 불변식을 기준으로 정리합니다.