leetcode medium : Minimum Time to Make Rope Colorful

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

Minimum Time to Make Rope Colorful - LeetCode

 

연속되는 컬러가 나오면 그 neededTime의 합 - 그중에 max값 을 정답에 추가하면 된다. 시간이 제일 오래걸리는거만 남겨두고 나머진 다 제거해야 로프가 컬러풀해지기 때문이다. 

 

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        answer = 0
        
        maxtime = neededTime[0]
        timesum = neededTime[0]
        
        for i in range(1, len(colors)):
            if colors[i] == colors[i-1]:
                maxtime = max(maxtime, neededTime[i])
                timesum += neededTime[i]
            else:
                if i >= 2 and colors[i-1] == colors[i-2]:
                    answer += timesum - maxtime
                timesum = maxtime = neededTime[i]
        
        if len(colors) > 2 and colors[-1] == colors[-2]:
            answer += timesum - maxtime
                
        return answer

정답 통과는 했지만 내 코드는 누가봐도 그냥 초보가 짠 코드같다. 고수가 짠 코드들을 보자.

 

def minCost(self, s, cost):
    res = max_cost = 0
    for i in xrange(len(s)):
        if i > 0 and s[i] != s[i - 1]:
            max_cost = 0
        res += min(max_cost, cost[i])
        max_cost = max(max_cost, cost[i])
    return res

진짜 아름다움. 기가차서 말이 안나옴..

컬러가 연속되는 구간에서 최소 2개 이상의 값들중에 max값을 찾고 현재 보고 있는 cost랑 비교해서 더 작은 값만 정답에 추가

 

int minCost(string s, vector<int>& cost) {
    int res = 0;
    for(int i=1; i<s.length(); i++) {
        if (s[i] == s[i-1]) {
            res += min(cost[i], cost[i-1]);
            cost[i] = max(cost[i], cost[i-1]);
        }
    }
    return res;
}

인풋 배열을 modify하는게 가능하다면 더 아름다워질 수 있음. (위의 파이썬 코드와 비슷한 방법인데 max값을 인풋배열에 저장한다는것만 다르다)

 

class Solution {
    public int minCost(String s, int[] cost) {
        int res = 0; int maxCost = cost[0];
        for(int i = 1; i < s.length(); i++)
        {        
            if(s.charAt(i) == s.charAt(i - 1))
            {
                //for duplicates, remove the letter that costs less
                res += Math.min(maxCost, cost[i]);
                //update the maxCost for the following possible duplicates: s[i + 2], s[i + 3], ...
                maxCost = Math.max(maxCost, cost[i]);
            }
            else
            {
                // if current letter is different from the previous one
                // update maxCost since current letter could be duplicated with following letters
                maxCost = cost[i];
            }
        }
        
        return res;
    }
}

굳이 인풋배열을 수정할 필요가 있느냐는 서양 개발자 형님

 

짝짝짝... 고수들의 코드.. 그저 구경만..ㅎ