문자열 s와 cost[i]가 s에서 i번째 문자를 삭제하는 비용을 나타내는 비용이라는 정수의 또 다른 배열이 있다고 가정합니다. 우리는 두 개의 같은 글자가 나란히 있지 않도록 최소 삭제 비용을 찾아야 합니다. 선택한 캐릭터를 동시에 삭제한다는 점을 염두에 두어야 합니다. 따라서 캐릭터를 삭제한 후에도 다른 캐릭터를 삭제하는 비용은 변하지 않습니다.
따라서 입력이 s ="pptpp", 비용 =[2,3,4,5,2]와 같으면 출력은 4가 됩니다. 왜냐하면 비용 2+2 =4로 첫 번째와 마지막 p를 제거하면 문자열은 "ptp"가 됩니다. 여기서 두 개의 동일한 문자가 차례로 표시되지 않습니다.
이 문제를 해결하기 위해 다음 단계를 따르겠습니다-
- 비용_f :=0
- i :=1
- ind :=0
- 범위 1에서 s - 1 크기의 i에 대해
- cur :=s[i], c_cost :=비용[i]
- 이전 :=s[i-1], p_cost :=비용[i-1]
- ind가 1과 같으면
- 이전:=prev_i, p_cost:=비용_i
- cur가 prev와 같으면
- c_cost>=p_cost이면
- 비용_f :=비용_f + p_비용
- 이전_i :=0, 비용_i :=0
- ind :=0
- c_cost
- 비용_f :=비용_f + c_비용
- ind :=1
- prev_i :=이전, 비용_i :=p_cost
- c_cost>=p_cost이면
- 그렇지 않으면
- 이전_i :=0, 비용_i :=0
- ind :=0
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(s, cost): cost_f = 0 i = 1 ind = 0 for i in range(1, len(s)): cur, c_cost = s[i], cost[i] prev, p_cost = s[i-1], cost[i-1] if ind == 1: prev, p_cost = prev_i, cost_i if cur == prev: if c_cost >= p_cost: cost_f += p_cost prev_i, cost_i = 0,0 ind = 0 if c_cost < p_cost: cost_f += c_cost ind = 1 prev_i, cost_i = prev, p_cost else: prev_i, cost_i = 0,0 ind = 0 return cost_f s = "pptpp" cost = [2,3,4,5,2] print(solve(s, cost))
입력
"pptpp", [2,3,4,5,2]
출력
4