Python에서 문자열을 반으로 단조롭게 만드는 데 필요한 업데이트 수를 찾는 프로그램

길이가 짝수인 소문자 문자열 s가 있다고 가정합니다. 모든 i에 대해 다음 세 가지 조건 중 하나가 충족되도록 업데이트해야 하는 최소 문자 수를 찾아야 합니다. 여기서 0 ≤ i

• s[i]> s[j]
• s[i]
• s[i] ==s[j]

따라서 입력이 s ="pppxxp"와 같으면 출력은 1이 됩니다. 왜냐하면 마지막 "p"를 "x"로 변경하면 s[i]

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

• n :=s의 크기
• left :=s의 왼쪽 절반부터 각 문자의 빈도를 포함하는 사전
• right :=s의 오른쪽 절반에서 각 문자의 빈도를 포함하는 사전
• an :=n
• 영문 소문자의 각 문자 피벗에 대해 다음을 수행합니다.
  • ans :=ans의 최소값 및 (n - 왼쪽[피벗] - 오른쪽[피벗])
  • good :=왼쪽에 있는 각 c에 대해 (left[c] if c <=pivot )에 있는 모든 요소의 합
  • good :=good + right에 있는 모든 요소의 합[c] if c> pivot
  • ans :=ans 및 (n - 양호)의 최소값
  • good :=왼쪽의 각 c에 대해 왼쪽[c]에 있는 모든 요소의 합계 if c> 피벗
  • good :=good + 오른쪽에 있는 모든 요소의 합[c] if c <=피벗
  • ans :=ans 및 (n - 양호)의 최소값
• 반환

예시

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

from collections import Counter
from string import ascii_lowercase
def solve(s):
   n = len(s)
   left = Counter(s[: n >> 1])
   right = Counter(s[n >> 1 :])

   ans = n
   for pivot in ascii_lowercase:
      ans = min(ans, n - left[pivot] - right[pivot])

      good = sum(left[c] for c in left if c <= pivot)
      good += sum(right[c] for c in right if c > pivot)
      ans = min(ans, n - good)

      good = sum(left[c] for c in left if c > pivot)
      good += sum(right[c] for c in right if c <= pivot)
      ans = min(ans, n - good)

   return ans

s = "pppxxp"
print(solve(s))

입력

"pppxxp"

출력

1