파이썬에서 문자열을 정렬하기 위한 최소 연산 수를 찾는 프로그램

<시간/>

문자열 s가 있다고 가정합니다. 정렬된 문자열을 얻을 때까지 s에 대해 다음 작업을 수행해야 합니다. -

1 <=i
[i, j] 포함 범위에서 가능한 모든 k 값에 대해 i <=j <길이 s 및 s[k]
인덱스 i - 1 및 j에서 두 문자를 교환합니다.
색인 i에서 접미사를 뒤집습니다.

문자열을 정렬하는 데 필요한 작업 수를 찾아야 합니다. 답은 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.

따라서 입력이 s ="ppqpp"와 같으면 출력은 2가 됩니다.

첫 번째 작업에서 i=3, j=4입니다. s[2] 및 s[4]를 교환하여 s="ppppq"를 얻은 다음 인덱스 3에서 하위 문자열을 반대로 합니다. 이제 s="pppqp"입니다.
두 번째 작업에서 i=4, j=4입니다. s[3] 및 s[4]를 교환하여 s="ppppq"를 얻은 다음 인덱스 4에서 하위 문자열을 반대로 합니다. 이제 s ="ppppq"입니다.

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

d :=크기가 26이고 0으로 채워진 배열
a :=0, t :=1
m :=10^9 + 7
n :='a'의 ASCII
s의 각 인덱스 i와 문자 c에 대해 역순으로 1부터 인덱스를 시작하고
- j :=c의 ASCII - n
- d[j] :=d[j] + 1
- a :=(a + d[인덱스 0에서 j-1까지]의 모든 요소의 합) * t/d[j]의 몫) mod m
- t :=t * i/d[j]의 몫
반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

def solve(s):
   d = [0]*26
   a = 0
   t = 1
   m = 10**9 + 7
   n = ord('a')
   for i,c in enumerate(s[::-1],1):
      j = ord(c) - n
      d[j] += 1
      a = (a+sum(d[:j])*t//d[j]) % m
      t = t*i//d[j]
   return a

s = "ppqpp"
print(solve(s))

로 반환

입력

"ppqpp"