C++에서 문자열 압축하기: 연속된 중복 문자 제거 알고리즘

문자열 s가 주어졌을 때, 이 문자열에서 연속으로 반복되는 문자를 모두 제거하고 결과를 반환하는 문제를 생각해 봅시다. 즉, 같은 문자가 여러 번 연달아 나타나면 하나의 문자만 남기고 나머지는 삭제하며, 문자들의 순서는 원래 그대로 유지해야 합니다.

예를 들어 입력이 "heeeeelllllllloooooo"라면, 출력은 "helo"가 됩니다.

문제 해결 접근 방법

이 문제는 문자열을 한 번만 순회하면서 직전 문자와 현재 문자를 비교하는 간단한 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.

• 결과를 저장할 빈 문자열 ret을 준비합니다.
• i를 0부터 문자열 s의 길이보다 작을 때까지 1씩 증가시키며 반복합니다.
• 각 반복에서 다음 조건을 확인합니다.
  • ret이 비어 있지 않고, ret의 마지막 문자가 현재 문자 s[i]와 같다면 → 현재 문자를 추가하지 않고 다음 반복으로 넘어갑니다(continue).
  • 그렇지 않다면 → 현재 문자 s[i]를 ret에 이어 붙입니다.
• 모든 문자를 확인한 후 최종적으로 ret을 반환합니다.

핵심 아이디어는 std::string의 back() 함수를 활용해 결과 문자열의 마지막 문자에 쉽게 접근하고, 새로 추가될 문자와 같은지 비교하는 것입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string solve(string s) {
        string ret = "";
        for(int i = 0; i < s.size(); i++){
            if(ret.size() && ret.back() == s[i]){
                continue;
            }
            ret += s[i];
        }
        return ret;
    }
};
int main(){
    Solution ob;
    cout << (ob.solve("heeeeelllllllloooooo"));
}

입력

"heeeeelllllllloooooo"

출력

helo

시간 및 공간 복잡도

• 시간 복잡도: O(n) — 문자열의 각 문자를 정확히 한 번씩만 확인하므로 매우 효율적입니다.
• 공간 복잡도: O(n) — 결과 문자열을 저장하기 위한 추가 공간이 필요합니다.

이처럼 단순한 순회와 조건 비교만으로도 연속 중복 문자를 손쉽게 제거할 수 있으며, 로그 데이터 정제나 사용자 입력 정규화 등 실무에서도 유용하게 활용될 수 있는 기본적인 문자열 처리 기법입니다.