Python으로 인접한 중복 문자 제거 시 최소 삭제 비용 구하는 방법

문제 개요

문자열 s와 정수 배열 cost가 주어집니다. 여기서 cost[i]는 s의 i번째 문자를 삭제할 때 드는 비용을 의미합니다. 우리가 구해야 하는 값은 문자열 안에 같은 문자가 두 개 연속으로 배치되지 않도록 만들기 위해 필요한 최소 삭제 비용입니다.

주의할 점은 선택한 문자들을 동시에 삭제한다는 것입니다. 따라서 어떤 문자를 삭제하더라도 다른 문자들의 삭제 비용은 변하지 않습니다.

예시로 이해하기

입력이 s = "pptpp", cost = [2,3,4,5,2]라고 가정해 봅시다. 이때 출력은 4입니다. 첫 번째 p와 마지막 p를 각각 비용 2씩, 총 2+2=4의 비용으로 제거하면 문자열이 "ptp"가 되어 연속된 동일 문자가 사라지기 때문입니다.

풀이 접근 방식

이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

문자열을 왼쪽에서 오른쪽으로 한 글자씩 훑으며 현재 문자(cur)와 바로 앞 문자(prev)를 비교합니다.
두 문자가 같다면 둘 중 삭제 비용이 더 작은 쪽을 제거하고 그 비용을 누적합니다.
앞 문자를 남기고 현재 문자를 지웠다면, 다음 비교에서도 "살아남은 문자"의 정보(prev_i, cost_i)를 이어받아야 하므로 이를 별도 변수로 관리합니다.
두 문자가 서로 다르다면 삭제 없이 다음 위치로 넘어갑니다.

알고리즘 단계

누적 비용 cost_f를 0으로, 플래그 ind를 0으로 초기화합니다.
i를 1부터 len(s)-1까지 순회하며 다음을 수행합니다.
- cur := s[i], c_cost := cost[i]
- prev := s[i-1], p_cost := cost[i-1]
- ind == 1이면(직전 문자가 이미 삭제된 상태라면) prev := prev_i, p_cost := cost_i로 대체합니다.
- cur == prev인 경우:
  - c_cost ≥ p_cost이면 → cost_f += p_cost, prev_i := 0, cost_i := 0, ind := 0
  - c_cost < p_cost이면 → cost_f += c_cost, ind := 1, prev_i := prev, cost_i := p_cost
- 그 외(두 문자가 다른 경우) → prev_i := 0, cost_i := 0, ind := 0
순회가 끝나면 cost_f를 반환합니다.

구현 예제

아래 코드를 통해 동작 방식을 더 잘 이해할 수 있습니다.

def solve(s, cost):
    cost_f = 0
    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
            else:
                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))

더 간결한 대안 구현

위 로직은 "연속된 같은 문자 구간에서는 가장 비싼 문자 하나만 남기고 나머지를 지운다"는 관점으로 단순화할 수 있습니다. 인접한 두 문자가 같을 때마다 더 싼 비용을 답에 더하고, 살아남은 문자의 비용을 다음 칸으로 전파하면 됩니다.

def solve(s, cost):
    total = 0
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            total += min(cost[i], cost[i-1])
            if cost[i] < cost[i-1]:
                cost[i] = cost[i-1]  # 남긴 문자의 비용을 전파
    return total

실행 결과

입력

"pptpp", [2,3,4,5,2]

출력

복잡도 분석

시간 복잡도: O(n) — 문자열을 한 번만 순회합니다.
공간 복잡도: O(1) — 추가 공간으로 상수 개의 변수만 사용합니다.