1578. Minimum Time to Make Rope Colorful

링크

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

푼 방법

이 문제는 그리디하게 풀 수 있습니다.

풀이의 핵심은 바로 연속된 동일한 알파벳이 존재하는 경우, 무조건 하나만 남기고 전부 다 터트려야 한다는 것입니다.

물론! 여기서 유의할 점은 하나는 남겨도 된다는 사실이에요.

그렇다면, 아래와 같은 핵심 개념이 나오게 될 것입니다.

연속된 풍선 중 neededTime이 가장 큰 것을 찾고, 이것을 제외하고 모두 다 터트린다. (즉, 1개만 남겨놓고 다 터트려야 합니다.)

이 정의에 맞춰 문제를 알고리즘을 구성하고 짜면 쉽게 풀 수 있습니다.

코드는 아래에 나와있으니, 코드 한줄 한줄에 대해서 코멘트를 남기지 않겠습니다.

유의할 사항

만일 해당 문제를 저와 같이 DP 로 접근한다면 해당 테스트 케이스에서 막힐 것입니다.

"bbbaaa" 
[4,9,3,8,8,9]

이 문제는 삭제했을 때 풍선이 빈 공간을 채워서 이동한다고 생각하시면 편할 것 같습니다.

이 문제에 대한 풀이를 적는 이유도 이것 때문입니다.

저는 처음에 Dp 문제라고 생각하고 이 문제에 접근했거든요.

그러고서 위 테스트 케이스에 막혀 다른 방법을 사용했습니다.

여러분들도 이 점을 유의하세요!

시간 복잡도

해당 풀이의 시간 복잡도는 O(N)

Correct Code

class Solution {
    
    public int minCost(String colors, int[] neededTime) {
        int answer = 0; 
        char pre = colors.charAt(0);
        int max = 0;
        int sum = 0;
        
        for (int i = 0; i < colors.length(); i++) { 
            char c = colors.charAt(i);
            
            if (pre != c) { 
                answer += (sum - max);
                sum = 0;
                max = 0;
                pre = c;
            } 
            
            sum += neededTime[i];
            max = Math.max(max, neededTime[i]);
        }
       
        answer += (sum - max);
        return answer;
    }
    
}