5509. Minimum Deletion Cost to Avoid Repeating Letters

Minimum Deletion Cost to Avoid Repeating Letters

Account Login - LeetCode

문제 질문 : 문자 배열을 주고 그배열에 대응하는 코스트 배열을 준다. 문자 배열에서 연속되는 글자가 있을 경우 코스트를 최소로 해서 연속글자를 삭제하고, 그 최소화된 코스트를 결과값으로 한다.

 

접근 방법 :

일단 대상이 연속되는 글자만 대상이여서 slow와 fast를 이용해서 Window를 만들었다.

예를 들어 'aaab'라고 하면 0부터 2까지의 인덱스만 확인하고 최소 코스트 값으로 a를 삭제 해 나가면 된다.

사실 이부분에 대한 이해를 잘 못해서 많은 시간을 썻다.

- 잘못 이해한 부분 : aaa 라고 하면 코스트가 [4,1,3]으로 대응 될경우 1만 return 하면 된다고 생각했다. 

그런데 문자 삭제 임으로 가운데 삭제 해도, a,a라는 값이 연속 되서 결국 다시 a 하나를 지워야 한다.

최종적으로 start~end index 사이 Max 코스트 값 [4,1,3] 이라고 하면 4만 남기고 1,3을 다 지워야 함으로

연속된 코스트를 전체 더하고 가장큰 코스트를 빼는 방법으로 풀었다.

var minCost = function(s, cost) {
    let slow = 0;
    let sum = 0;
    let sArr = s.split('');
    sArr.push('_');
    
    for(let fast = 1; fast < sArr.length;fast++){
        if(sArr[slow] !== sArr[fast]){
            if(0 < fast - slow - 1){
                sum += findMin(slow,fast-1,cost);
            }
            slow = fast;
        }
    }
    
    return sum;
    
    
    function findMin(start,end,cost){
        if(end <= start) return 0;
            
        let max = 0;
        let sum = 0;
        
        
        for(let i = start; i <= end; i++){
            sum += cost[i];
            max = Math.max(max,cost[i]);
        }
        
        return sum - max;
        
    }
    
};

 

plus : 내가 잘못 생각했던 문제의 방법으로 푼 문제 풀이를 아래 붙힌다.

문제 질문이 다음과 같이 바뀌면 아래 답이 맞다.

문자 배열을 주고 그배열에 대응하는 코스트 배열을 준다. 문자 배열에서 연속되는 글자가 있을 경우 코스트를 최소로 해서 연속글자를 대체하는 위치의 최소화된 코스트를 결과값으로 한다.

즉 코스트 값이 [3,9,3] 이 있으면 3과 3 = 6을 결과 값으로 하는 방법이다.

[1,1,1,4] 이면 2가 결과 값이 된다.

해당 방법은 permutation을 사용해서 나올수 있는 모든 경우에 수의 min값을 계산했다.

Math.min(왼쪽 배열 최소 코스트 + 현재값 코스트 + 오른쪽 배열 최소 코스트)

본 문제의 취지가 아니었는데, 잘못된 질문 이해로 문제를 한단계 더 어렵게 만들었다.

var minCost = function(s, cost) {
    let slow = 0;
    let sum = 0;
    let sArr = s.split('');
    sArr.push('_');
    
    for(let fast = 1; fast < sArr.length;fast++){
        if(sArr[slow] !== sArr[fast]){
            if(0 < fast - slow - 1){
                sum += findMin(slow,fast-1,cost);
            }
            slow = fast;
        }
    }
    
    return sum;
    
    
    function findMin(start,end,cost){
        if(end <= start) return 0;
            
        let max = 0;
        let sum = 0;
        
        
        for(let i = start; i <= end; i++){
            min = Math.min(min, findMin(start,i-1,cost) + cost[i] + findMin(i+1,end,cost));
        }
        
        return sum - max;
        
    }
    
};