[LeetCode][Python]1578. Minimum Time to Make Rope Colorful

https://leetcode.com/problems/minimum-time-to-make-rope-colorful/description/?envType=daily-question&envId=2023-12-27

Minimum Time to Make Rope Colorful - LeetCode

Alice가 같은 색상의 풍선이 있는게 보기 싫어서 Bob한테 떼달라고한다.

근데 Bob은 같은 색상 풍선인데도 풍선떼는 시간이 달라서 최소한의 시간으로 떼고 싶다고 한다.

풍선 line과 떼는 시간을 제공할테니, 최소시간을 구해라.

---

 

https://baseballgrammer.tistory.com/70

1일차 - 그리디

에 작성한 전형적인 그리디 유형이다.

 

문제에 틀을 잡는데에 editorial을 참고했다.

 

풍선 line은 문자열로 주어지는데, 그 문자열을 반복문을 통해서 문자를 하나씩 읽어서

그 문자가 그 전에 문자와 같지않다면 즉, 풍선이 다른 색상이라면 떼는 시간을 생각하지 않는다.(풍선을 떼는데에 사용할 최대시간 = 0)

        for i in range(len(colors)):
            if i > 0 and colors[i] != colors[i-1]:
                current_max = 0

 

그리고 요구되는 시간과 풍선을 떼는데에 사용할 최대시간 중

최솟값을 정답에 더하고,

최댓값을 풍선을 떼는데에 사용할 최대시간으로 변경하면 되겠다.

            answer += min(current_max, neededTime[i])
            current_max = max(current_max, neededTime[i])

 

 

정답코드이다.

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        answer = 0
        current_max = 0

        for i in range(len(colors)):
            if i > 0 and colors[i] != colors[i-1]:
                current_max = 0

            answer += min(current_max, neededTime[i])
            current_max = max(current_max, neededTime[i])
        return answer