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

1578번 문제 링크

https://leetcode.com/problems/minimum-time-to-make-rope-colorful/

Minimum Time to Make Rope Colorful - LeetCode

문제설명

입력: colors 문자열, neededTime 정수 배열 

출력: 풍선제거 최소시간

Alice는 같은 색깔의 풍선이 2개 이상 연속되는 것을 싫어한다고 한다. (성질 머리 하고는..)

Bob에게 연속된 풍선을 제거 요청했다고 한다. 각 풍선마다 제거 하는데 걸리는 시간이 배열로 주어진다.

풍선 제거 시간이 최소가 되는 시간을 output으로 내면 된다.

문제예제

3번째, 4번째 풍선이 둘다 파란색으로 겹친다.

neededTime을 보면 각각 3초, 4초가 걸린다.

풍선 제거에 최소시간을 구해야 하기에 3초를 선택하여

답은 3이 된다.

 

문제풀이

1. 연속된 색깔의 시작점을 잡아준다. (for문 안에서 colors[i] == colors[i+1] 비교 필요)

2. 연속된 색깔이 2개 이상으로 계속 될 수 있기에 연속된 색이 끝나는 지점을 잡아준다.

3. first = 연속된 색 시작지점, last = 연속된 색 끝나는지점이라고 놨을때,

neededTime[ first : last + 1] 에서 풍선 하나만 빼고 다 제거 해야한다.

그렇다면 시간이 제거 시간이 가장 오래 걸리는 것 빼고 다 제거한다.

4. 풍선 제거 시간 = sum(neededTime[ first : last + 1]) - max(neededTime[ first : last + 1])

5. (총 풍선 제거 걸린시간)에 (풍선 제거시간)을 더해준다.

6. 마지막으로 return 총 풍선 제거 걸린 시간

 

정답코드

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        N = len(colors)
        flag = True
        ans = 0
        f,l = 0,0
        for i in range(0, N-1):
            if colors[i] == colors[i+1]:# 색이 연속적으로 같을 때
                if flag == True:        # 연속된 색의 시작 위치를 한번 잡아줌
                    f = i               # 연속된 색의 시작 위치
                    flag = False       
                l = i + 1               # 연속된 색의 마지막 위치 설정     
            else:
                flag = True
                if l != 0:
                    # 연속된 색깔 중 제거하는데 필요한 시간이 가장 오래걸리는 것만 남기고 제거해줌.
                    ans += sum(neededTime[f:l+1]) - max(neededTime[f:l+1])
                l = 0
                
        if l != 0:  # 마지막이 연속된 값으로 끝났을 때, ans에 더해줘야 하기 때문에
            ans += sum(neededTime[f:l+1]) - max(neededTime[f:l+1])
        return ans

시간복잡도: O(N)

 

풀이 후 생각정리

연속된 풍선의 색을 1개만 놔두고 지워야 하기 때문에, 연속된 풍선의 배열의 index의 시작과 끝을 찾으려고 했다.

시작과 끝을 찾아서 neededTime 배열에서 (연속된 풍선을 제거하는데 걸리는 시간 총합) - (제거하는데 가장 오래걸리는 풍선) 을 해주면 연속된 풍선을 1개만 두고 제거하는데 최소 시간을 구할 수 있었다.

문제만 보고 어려워 보였는데, 생각보다 쉬운 문제였다.

문제를 정확하게 파악하고 어떤 방식으로 해결할지 차근차근 생각하면 누구나 풀 수 있는 문제 같다!