[LeetCode] 1578. Minimum Time to Make Rope Colorful

1578. Minimum Time to Make Rope Colorful

Medium

Alice has n balloons arranged on a rope. You are given a 0-indexed string colors where colors[i] is the color of the ith balloon.

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.

 

Example 1:

Input: colors = "abaac", neededTime = [1,2,3,4,5]
Output: 3
Explanation: In the above image, 'a' is blue, 'b' is red, and 'c' is green.
Bob can remove the blue balloon at index 2. This takes 3 seconds.
There are no longer two consecutive balloons of the same color. Total time = 3.

Example 2:

Input: colors = "abc", neededTime = [1,2,3]
Output: 0
Explanation: The rope is already colorful. Bob does not need to remove any balloons from the rope.

Example 3:

Input: colors = "aabaa", neededTime = [1,2,3,4,1]
Output: 2
Explanation: Bob will remove the ballons at indices 0 and 4. Each ballon takes 1 second to remove.
There are no longer two consecutive balloons of the same color. Total time = 1 + 1 = 2.

 

Constraints:

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

---

문제 풀이

• 풍선의 알파뱃이 컬러를 의미하고, 풍선을 치울때 얼만큼 시간이 드는지 리스트가 주어진다. 
• 풍선이 색이 연속적으로 겹쳐지지 않게 만들어야 하며, 결과물을 완성했을때 사용한 시간을 최소화 해야한다. 
• 풍선의 최대 갯수는 10^5 이기 때문에 최악의 경우에는 시간복잡도 N^2 을 가진 알고리즘으로 풀 수 없다. 
• O(NlogN) 혹은 O(N) 으로 풀어야하는데, 풍선이 연속으로 있을때 무조건 하나만 남기게 만들 수 있다면 풀이가 가능하다. 
• 즉, 다른 색의 풍선이 같은 색 풍선 사이에 존재만 한다면 알록달록이 성립하기 때문이다. 
• 두가지 접근방법이 있다, Deque 를 사용하는 방법과 Two Pointer 를 이용하는 방법이다.

 

• Deque
  • 풍선을 큐에 하나씩 넘기면서, 덱큐의 뒤 값과 리스트의 값을 비교해가면서 풍선을 처리한다. 
  • 덱큐 끝에 있는 풍선의 처리비용이 작다면 리스트의 풍선의 처리비용을 더하고 아무 처리하지 않는다. 
  • 리스트의 풍선비용이 작다면 덱큐의 맨 마지막 풍선의 처리비용을 더하고 덱큐에서 맨뒤 풍선을 빼고 리스트의 풍선을 넣는다. 
• Two Pointer
  • Two Pointer 방법은 리스트의 처음부터 두 번째 포인터를 같은 색깔 풍선이 있는곳 까지 옮겨야한다.
  • 옮기는 도중에, 같은 색 풍선들의 처리비용들을 모두 더하면서 처리비용의 최대값을 구해놓는다.
  • 다른 색의 풍선이 나왔을때 전체 답에서 같은 색 풍선들의 처리비용 합 - 최대 처리비용을 제거하고 더해준다. 
  • 이는, 가장 큰 처리비용이 드는 풍선을 하나 남기고 모두 제거하는 것이라고 볼 수 있다. 

 

소스 코드

Deque

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        l_q = deque()
        l_q.append((colors[0], 0))
        ans = 0
        for i in range(1, len(colors)):
            if l_q[-1][0] == colors[i]:
                if neededTime[l_q[-1][1]] > neededTime[i]:
                    ans += neededTime[i]
                else:
                    temp = l_q[-1][1]
                    l_q.pop()
                    l_q.append((colors[i], i))
                    ans += neededTime[temp]      
            else:
                l_q.append((colors[i], i))
        return ans

Two Pointer

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        total = 0
        p1, p2 = 0, 0
        
        while p1 < len(neededTime) and p2 < len(neededTime):
            curr_total = 0
            curr_max = 0
            
            while p2 < len(neededTime) and colors[p1] == colors[p2]:
                curr_total += neededTime[p2]
                curr_max = max(curr_max, neededTime[p2])
                p2 += 1
            total += curr_total - curr_max
            p1 = p2
        return total