1. 문제 소개

Constraints:

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

1578. Minimum Time to Make Rope Colorful

2. 나의 풀이법

처음 생각한 풀이는 colors를 한 번 순회하여 이전과 이후의 색깔이 같은 경우 더 짧은 시간이 걸리는 쪽을 제거하는 방향으로 진행했다.
그러나 처음에는 colors = "aaabbbabbbb"이고 neededTime = [3,5,10,7,5,3,5,5,4,8,1]인 경우에서 틀렸는데, 이는 연속된 2개만 비교해서 생기는 문제였다. 구간 내부에서 최대값을 제외한 합을 구해야 풀리는 문제였기에 다시 풀었고 정답을 맞출 수 있었다.
시간복잡도는 $O(n)$이다.

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        ans = 0
        keep = neededTime[0]
        for i in range(len(colors) - 1):
            if colors[i] == colors[i+1]:
                ans += min(keep, neededTime[i+1])
                keep = max(keep, neededTime[i+1])
            else:
                keep = neededTime[i+1]
        return ans

3. 다른 풀이법

투 포인터를 사용하는 방식도 존재한다.
i와 j를 이용해 연속된 구간을 찾고, 그 구간에서 최대값을 제외하는 방식이다.
이 또한 시간복잡도는 $O(n)$이다.

class Solution:
    def minCost(self, colors: str, neededTime: list[int]) -> int:
        total_time = 0
        i = 0
        j = 0

        while i < len(neededTime) and j < len(neededTime):
            curr_total = 0
            curr_max = 0

            while j < len(neededTime) and colors[i] == colors[j]:
                curr_total += neededTime[j]
                curr_max = max(curr_max, neededTime[j])
                j += 1

            total_time += curr_total - curr_max
            i = j

        return total_time

4. 결론

min(), max()를 사용하지 않고 등호를 이용하면 조금 더 빠르게 풀 수도 있다.