Python으로 문자열의 연속 중복 문자 제거하기

문제 정의

'R'과 'L'로만 구성된 문자열 s가 주어졌다고 가정해 보겠습니다. 우리가 해야 할 일은 최소한의 문자만 제거하여 연속된 'RR'이나 'LL'이 나타나지 않도록 만드는 것입니다.

예를 들어 입력이 "LLLRLRR"이라면, 출력은 "LRLR"이 됩니다. 즉, 앞부분의 연속된 'LL' 두 개와 뒷부분의 연속된 'RR' 하나를 제거한 결과입니다.

해결 접근 방법

이 문제는 간단한 그리디(Greedy) 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 문자열을 한 번만 순회하면서 직전 문자와 현재 문자를 비교하는 것입니다.

• seen: 마지막으로 결과에 포함시킨 문자를 저장하는 변수입니다.
• ans: 최종 결과 문자열로, 첫 번째 문자로 초기화합니다.
• 인덱스 1부터 문자열 끝까지 각 문자 i에 대해 반복합니다.
  • i가 seen과 다르면 ans에 i를 추가하고 seen을 i로 갱신합니다.
  • i가 seen과 같다면 연속 중복이므로 건너뜁니다.
• 반복이 끝나면 ans를 반환합니다.

이 방법은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도 역시 결과 저장을 위해 O(n)입니다.

구현 예제

class Solution:
    def solve(self, s):
        seen = s[0]
        ans = s[0]
        for i in s[1:]:
            if i != seen:
                ans += i
                seen = i
        return ans

ob = Solution()
print(ob.solve("LLLRLRR"))

입력

"LLLRLRR"

출력

LRLR

동작 원리 살펴보기

입력 "LLLRLRR"에 대해 위 코드가 어떻게 동작하는지 단계별로 확인해 보겠습니다.

• 첫 번째 문자 'L'로 seen과 ans를 초기화합니다.
• 두 번째, 세 번째 문자도 'L'이므로 seen과 같아 건너뜁니다.
• 네 번째 문자 'R'은 seen('L')과 다르므로 추가합니다 → ans = "LR"
• 다섯 번째 문자 'L'은 'R'과 다르므로 추가합니다 → ans = "LRL"
• 여섯 번째, 일곱 번째 문자 'R', 'R' 중 첫 번째 'R'만 추가하고 두 번째는 건너뜁니다 → ans = "LRLR"

최종적으로 "LRLR"이 반환되며, 어떤 위치에도 연속된 동일 문자가 존재하지 않음을 확인할 수 있습니다.