Python에서 문자열 균형을 맞추기 위해 최소 삭제를 찾는 프로그램

<시간/>

두 개의 문자 ''와 't'만 있는 문자열 s가 있다고 가정합니다. 문자열의 균형을 맞추기 위해 의 문자를 원하는 만큼 삭제할 수 있습니다. i

따라서 입력이 s ="sststtst"와 같으면 인덱스 2와 6에서 문자를 제거하거나("sststtst"에서 "sssttt"로) 인덱스 3에서 문자를 제거할 수 있기 때문에 출력은 2가 됩니다. 6("sststtst"에서 "sstttt"까지).

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

cum_b :=0
count_a :=s의 's' 문자 수
ans :=무한대
s의 각 x에 대해 수행
- x가 "s"와 같으면
  - count_a :=count_a - 1
  - ans :=ans의 최소값 및 (cum_b + count_a)
- 그렇지 않으면
  - cum_b :=cum_b + 1
  - ans :=ans의 최소값 및 (cum_b-1 + count_a)
반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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"