[리트코드] 1578. Minimum Time to Make Rope Colorful

1578. Minimum Time to Make Rope Colorful

문제 설명

Alice wants the rope to be colorful. She does not want two consecutive balloons to be of the same color, so she asks Bob for help. Bob can remove some balloons from the rope to make it colorful. You are given a 0-indexed integer array neededTime where neededTime[i] is the time (in seconds) that Bob needs to remove the ith balloon from the rope.

Return the minimum time Bob needs to make the rope colorful.

반복되는 구간을 최소 비용으로 지우기

제한 조건

• n == colors.length == neededTime.length
• 1 <= n <= 105
• 1 <= neededTime[i] <= 104
• colors contains only lowercase English letters.

풀이

반복되는 구간을 찾아서 비용이 가장 큰 것만 남기고 제거한다.

1. 이전 값과 다른 부분을 찾는다.

1. 그 앞의 부분 배열의 총 합에서 최대값만 뺀 나머지를 결과에 더한다.

연속되지 않을 때를 조건으로 제거하다보니 마지막에 연속된 문자가 몰려 있을 때 실패하는 경우가 생겼다. 그래서 문자열 마지막에 "!"를 붙여서 한번 더 계산할 수 있도록 했다.

예)

"aabaa" [1,2,3,4,1]

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        prev = 0
        result = 0
        colors += "!"
        
        for i in range(1, len(colors)):
            if colors[prev] != colors[i]:
                if (i - prev) > 1:
                    result += sum(neededTime[prev: i]) - max(neededTime[prev: i])
                prev = i
        
        return result

부분 배열을 구하는 것보다는 하나씩 비용을 더해가면서 연속된 문자인지 확인하는 방식이 더 효율적이다.

• 연속일 경우 sum_cost와 max_cost를 갱신한다.

• 연속이 끝날 경우 sum_cost와 max_cost를 0으로 초기화 해주고 제거 비용을 더한다.
• 남은 sum_cost와 max_cost를 더해준다.

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        result = 0
        sum_cost = 0
        max_cost = 0
        for i in range(0, len(colors)):
            if i != 0 and colors[i- 1] != colors[i]:
                result += sum_cost - max_cost
                sum_cost = max_cost = 0
            
            sum_cost += neededTime[i]
            max_cost = max(max_cost, neededTime[i])
            
        result += sum_cost - max_cost;
        return result