Leetcode) Earliest Possible Day of Full Bloom

2136. Earliest Possible Day of Full Bloom

class Solution:
    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:        
        day = 0
        totalPlant = 0
        for plant, grow in sorted(zip(plantTime, growTime), key=lambda x: -x[1]):
            totalPlant += plant
            day = max(day, totalPlant + grow)
                
        return day

문제는 Greedy하게 풀어야 했으며 이 메커니즘에 대해 이해 해야햇습니다.

1. 모든 씨앗은 그 전에 심은 씨앗들의 plantTime을 다 더한 것보다 day가 커야 심을 수 있다.
2. 그렇다면 어떻게 해야 가장 optimal하게 심을 수 있을까?
3. 가장 중요한 것이 씨앗이 자라는 동안 다른 씨앗들이 plantTime을 가질 수 있도록 하는 것이다.
4. 그럴려면 가장 growTime이 긴 것 씨앗 부터 심는다.
5. 그런데 plantTime의 누적 시간을 저장하면서 진행합니다.
6. 그리고 day,totalPlant + growTime중에 큰 값을 day로 저장하는 이유는 이 씨앗이 다른 씨앗들 이전에 심어 질 수 있는지 판단하는 것이다.
7. day - totalPlant자체가 내가 자유롭게 이용할 수 있는 공간이라는 의미가 되기 때문이다.
8. 그래서 이런 식으로 day를 저장해가면 자연스럽게 빈 공간 없이 optimal하게 씨앗을 심을 수 있게 됩니다.