[LeetCode] 1578. Minimum Time to Make Rope Colorful

https://leetcode.com/problems/minimum-time-to-make-rope-colorful/description/?envType=daily-question&envId=2023-12-27

Minimum Time to Make Rope Colorful - LeetCode

leetcode - 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.

 

앨리스는 n개의 풍선을 한 로프에 나열한 것을 가지고 있습니다.

당신은 colors[i] = i번째 풍선의 색깔 정보를 담은 문자열 colors를 받습니다.

앨리스는 로프가 알록달록하길 바랍니다. 두 인접한 풍선의 색이 서로 다르길 바랍니다.

밥은 로프에서 풍선을 제거할 수 있습니다.

당신은 neededTime[i] = i번째 풍선을 지우는데 걸리는 시간인 정수 배열 neededTime을 받습니다.

알록달록한 로프를 만들기 위한 최소 시간을 구하시오.

 

 

풀이

문자열에서 같은 문자가 나오는 그룹들별로 분류하여 찾는다.

그 뒤, 그 그룹의 제거시간의 총합에서 가장 오래걸리는 풍선을 제외하고 누적시킨다.

이 과정을 반복하면 된다.

 

그룹별로 한 풍선은 남겨야 하므로, 가장 오래걸리는 풍선을 제외하고 누적시키는 것이다.

 

 

코드

C++

static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minCost(string colors, vector<int>& neededTime) {
        const int n = colors.size();
        
        // 인덱스 및 전체시간 초기화
        int idx = 0;
        int sum = 0;

        while(idx < n) {
        	// 그룹 총합 초기화 미치 가장 큰 수 초기화
            int groupSum = 0;
            int maxNum = -1e9;
            // 다음것과 같은동안 계속 그룹 총합 누적 및 큰 수 갱신
            while(idx < n && colors[idx] == colors[idx+1]) {
                groupSum += neededTime[idx];
                maxNum = max(maxNum, neededTime[idx]);
                idx++;
            }
            // 마지막 그룹 수까지 처리
            groupSum += neededTime[idx];
            maxNum = max(maxNum, neededTime[idx]);

			// 가장 오래걸리는 것 제외하고 전부 없애기
            sum += groupSum-maxNum;
            idx++;
        }
        return sum;
    }
};