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

LeetCode 1578번 Minimum Time to Make Rope Colorful 문제는 여러가지 색의 풍선이 나열되어 있을 때 같은 색의 풍선이 연속해서 나오지 않도록 만드는 문제다. 난이도는 중(Medium)이며 그리디 알고리즘을 통해 해결할 수 있다.

 

리트코드 1578번 Minimum Time to Make Rope Colorful 문제 정보

알고리즘 분류

- Greedy

난이도

- Medium

 

문제 요약

• 다양한 색의 풍선이 한줄로 놓여있다.
• 각 풍선을 없애는 데 필요한 시간이 배열로 주어진다.
• 전체 풍선 중 같은 색의 풍선이 연속해서 나오지 않도록 하는 데 걸리는 최소 시간을 구하라.

 

문제 풀이 과정

 

• n ≤ 10000이므로 O(n^2) 아슬아슬함
• 그냥 쭉 보면서 같은색이 여러번 나오면 그 중에서 가장 비용이 큰 풍선 빼고 모두 없앤다.

코드

class Solution:
    def get_min(self, times:List[int]) -> int:
        return sum(times) - max(times)
    
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        answer = 0
        
        pre_color = ""
        consecutive_len = 1
        
        for idx, color in enumerate(colors):
            if pre_color == color:
                consecutive_len += 1
            else:
                if consecutive_len > 1:
                  answer += self.get_min(neededTime[idx-consecutive_len:idx])  
                pre_color = color
                consecutive_len = 1
        
        if consecutive_len > 1:
          answer += self.get_min(neededTime[-consecutive_len:])  
        
        return answer

• 시간복잡도: for문: O(n), get_min() 함수: O(n)이지만 get_min이 많이 일어나봐야 다 합쳐서 O(n)임 (for문마다 O(n)씩 일어나는거 아님)
• 공간복잡도: O(1)