Python으로 문자열 균형을 맞추는 최소 삭제 횟수 찾기

's'와 't' 두 문자로만 이루어진 문자열 s가 있다고 가정해 봅시다. 문자열을 균형 잡힌 상태로 만들기 위해 임의의 개수만큼 문자를 삭제할 수 있습니다.

문제 이해하기

문자열 s가 균형 잡혔다(balanced)는 것은 i < j이면서 s[i] = 't'이고 s[j] = 's'를 만족하는 인덱스 쌍 (i, j)이 존재하지 않는 경우를 의미합니다. 쉽게 말해, 어떤 's'보다 앞쪽에 't'가 나타나서는 안 된다는 뜻입니다. 우리가 구해야 할 값은 s를 균형 잡히게 만들기 위해 필요한 최소 삭제 횟수입니다.

예를 들어 입력이 s = "sststtst"라면 출력은 2가 됩니다. 인덱스 2와 6의 문자를 제거하여 "sssttt"로 만들거나, 인덱스 3과 6의 문자를 제거하여 "sstttt"로 만들 수 있기 때문입니다.

접근 방법

핵심 아이디어는 다음과 같습니다. 균형 잡힌 문자열은 결국 모든 's'가 모든 't'보다 앞에 오는 "sss...ttt" 형태가 됩니다. 따라서 문자열 내의 각 위치를 분할 지점으로 삼아 아래처럼 처리하면 항상 균형 잡힌 문자열을 얻을 수 있습니다.

• 분할 지점 앞쪽에 있는 모든 't'를 삭제

• 분할 지점 뒤쪽에 있는 모든 's'를 삭제

모든 분할 지점에 대해 (앞의 't' 개수 + 뒤의 's' 개수)를 계산하고, 그중 최솟값이 곧 정답이 됩니다. 알고리즘의 구체적인 단계는 다음과 같습니다.

• cum_b := 0 (지금까지 확인한 't'의 개수)

• count_a := s에 포함된 's' 문자의 개수

• ans := 무한대(infinity)

• s의 각 문자 x에 대해 반복:

  • x가 "s"라면 → count_a를 1 감소시키고, ans := min(ans, cum_b + count_a)

  • 그렇지 않다면("t"라면) → cum_b를 1 증가시키고, ans := min(ans, cum_b − 1 + count_a)

• ans 반환

구현 예시

이해를 돕기 위해 파이썬 구현 코드를 살펴보겠습니다.

def solve(s):
   cum_b = 0
   count_a = s.count("s")
   ans = float("inf")
   for x in s:
      if x == "s":
         count_a -= 1
         ans = min(ans, cum_b + count_a)
      else:
         cum_b += 1
         ans = min(ans, cum_b - 1 + count_a)
   return ans

s = "sststtst"
print(solve(s))

입력

"sststtst"

출력

2

복잡도 분석

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 역시 상수 공간 O(1)만 사용합니다. 따라서 길이가 매우 긴 문자열에도 효율적으로 동작합니다.