C++로 연속 중복 문자를 제거하는 최소 비용 구하기

문제 개요

소문자로만 구성된 문자열과, 문자열과 길이가 같은 음수가 아닌 정수 배열 costs가 주어졌다고 가정해 보겠습니다. 우리는 비용 costs[i]를 지불하여 문자 s[i]를 삭제할 수 있으며, 삭제가 일어나면 s[i]와 costs[i]가 모두 제거됩니다. 이때 문자열에 연속으로 반복되는 문자가 남지 않도록 만들기 위해 필요한 최소 비용을 구하는 것이 목표입니다.

예를 들어 입력이 s = "xxyyx", nums = [2, 3, 10, 4, 6]이라면 출력은 6이 됩니다. s[0]을 비용 2로, s[3]을 비용 4로 삭제하면 총비용이 2 + 4 = 6이 되며, 이후 문자열에는 연속 중복 문자가 존재하지 않게 됩니다.

접근 방법: 스택 활용

이 문제는 스택을 사용하면 한 번의 순회로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 연속된 동일한 문자 그룹 중에서 비용이 가장 큰 문자 하나만 남기고 나머지는 모두 삭제하는 것입니다. 알고리즘은 다음과 같습니다.

정수형 스택 st를 하나 선언합니다.
총비용 cost를 0으로 초기화합니다.
i를 0부터 문자열 길이까지 순회하면서 다음을 수행합니다:
- 스택이 비어 있지 않고 s[스택 top]이 s[i]와 같다면:
  - nums[top] > nums[i]인 경우: 현재 문자가 더 저렴하므로 cost에 nums[i]를 더합니다.
  - 그렇지 않은 경우: 기존 문자가 더 저렴하거나 같으므로 cost에 nums[top]을 더하고, 스택에서 pop한 뒤 i를 push합니다.
- 그 외의 경우에는 인덱스 i를 스택에 push합니다.
순회가 끝나면 cost를 반환합니다.

즉, 연속된 문자를 만날 때마다 두 비용을 비교하여 더 작은 쪽을 삭제 비용에 누적하고, 스택에는 항상 해당 그룹에서 살아남은(비용이 큰) 문자의 인덱스만 유지됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

class Solution {
    public:
    int solve(string s, vector<int>& nums) {
        stack<int> st;
        int cost = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (st.size() && s[st.top()] == s[i]) {
                if (nums[st.top()] > nums[i]) {
                    cost += nums[i];
                } else {
                    cost += nums[st.top()];
                    st.pop();
                    st.push(i);
                }
            } else {
                st.push(i);
            }
        }
        return cost;
    }
};

int solve(string s, vector<int>& nums) {
    return (new Solution())->solve(s, nums);
}

main(){
    vector<int> v = {2, 3, 10, 4, 6};
    string s = "xxyyx";
    cout << solve(s, v);
}

실행 결과

입력:

"xxyyx", {2, 3, 10, 4, 6}

출력:

복잡도 분석

이 알고리즘은 문자열을 딱 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 최악의 경우 모든 인덱스가 스택에 저장될 수 있으므로 O(n)입니다. 스택을 활용한 그리디 방식으로 각 연속 그룹에서 최소 삭제 비용을 보장할 수 있다는 점이 이 풀이의 핵심입니다.