파이썬으로 k개 연속 중복 문자를 반복 삭제한 후 최종 문자열 구하기

문자열 s와 정수 k가 주어졌을 때, 문자열에서 k개가 연속으로 이어진 중복 문자를 더 이상 찾을 수 없을 때까지 반복해서 삭제한 뒤, 최종 남은 문자열을 반환하는 문제입니다.

문제 이해하기

예를 들어 입력이 s = "paaappmmmma", k = 3이라고 가정해 보겠습니다. 이때 기대되는 출력은 "ma"입니다.

• 먼저 연속된 세 개의 "a"를 삭제하면 "pppmmmma"가 됩니다.
• 다음으로 연속된 세 개의 "p"를 삭제하면 "mmmma"가 됩니다.
• 마지막으로 네 개의 "m" 중 연속된 세 개를 삭제하면 "ma"가 됩니다.

이처럼 각 단계에서 k개씩 묶어 중복 문자를 제거하는 과정을 반복해야 합니다.

해결 접근 방법

이 문제는 다음과 같은 순서로 해결할 수 있습니다.

• 무한 루프를 돌며 아래 과정을 반복합니다.
  • count := 0 으로 초기화합니다.
  • chars := 문자열 s에서 고유한 문자들을 추출합니다.
  • chars의 각 문자 c에 대해 다음을 수행합니다.
    • 만약 c가 k번 연속 등장하는 부분이 s에 존재한다면
      • s에서 해당 부분(k개 연속 c)을 삭제합니다.
      • count 값을 1 증가시킵니다.
  • 만약 count가 0이라면(더 이상 삭제할 부분이 없다면)
    • 루프를 빠져나옵니다.
• 최종 문자열 s를 반환합니다.

파이썬 구현 예제

class Solution:
   def solve(self, s, k):
      while True:
         count = 0
         chars = set(s)
         for c in chars:
            if c * k in s:
               s = s.replace(c * k, "")
               count += 1
         if count == 0:
            break
    return s

ob = Solution()
s = "paaappmmmma"
k = 3
print(ob.solve(s, k))

입력

"paaappmmmma", 3

출력

ma

코드 설명

위 코드에서 핵심은 c * k 표현식입니다. 파이썬에서는 문자열에 곱셈 연산자를 사용하면 해당 문자를 k번 반복한 문자열을 손쉽게 만들 수 있습니다. 이를 in 연산자로 검사하여 연속 중복 여부를 확인하고, replace() 메서드로 삭제를 수행합니다.

한 번의 순회에서 삭제가 하나라도 일어났다면(count > 0), 문자열이 변경되었으므로 새로운 연속 중복 패턴이 생겼을 가능성이 있습니다. 따라서 while 루프를 통해 삭제가 전혀 발생하지 않을 때까지 전체 과정을 반복하는 것이 이 알고리즘의 핵심 로직입니다.