[CodingNinjas] 3167805. Minimum Deletion Cost to Avoid Repeating Letters

문제

3167805. Minimum Deletion Cost to Avoid Repeating Letters

풀이 1. 단순 구현

def minimumCost(n, s, cost) -> int:
    answer=0
    costSum=0
    maxCost=0
    for i in range(n):
        if (i>0 and s[i-1] != s[i]):
            answer+=(costSum-maxCost)
            costSum=0
            maxCost=0
        
        #update 'costSum' and 'maxCost'
        costSum+=cost[i]
        maximumCost = max(maximumCost, cost[i])
        
    return answer

풀이 2. Dictionary

def solution(S,C):
    ch_dict = {}
    key_track = -1
    min_cost = 0
    
    for idx, ch in enumerate(S):
        # first start -> 1. put into dictionary
        if idx==0:
            ch_dict[idx] = []
            key_track = idx
        else:
            # 2. put into dictionary
            if S[idx-1]!=S[idx]:
                ch_dict[idx] = []
                key_track = idx

            if S[idx-1]==S[idx]:
                ch_dict[key_track].append(idx)
                
    for k, v in ch_dict.items():
        # 아무것도 없을 때는 그냥 넘어가도 됌
        if len(v) == 0:
            continue
        else:
            temp = v
            temp.append(k)
            temp = [C[i] for i in temp] # O(n^2)이 되네..
            min_cost += sum(temp)-max(temp)
    
    return min_cost

결과 확인

if __name__ == "__main__":
    S="aabbcc"
    C=[3,4,5,6,7,8]
    cost = solution(S, C)
    print("cost: ", cost)

cost: 15