문제 설명
문자열 s가 주어졌을 때, 문자열이 완전히 정렬된 상태가 될 때까지 다음과 같은 연산을 반복해서 수행해야 합니다.
1단계: 1 ≤ i < len(s)를 만족하면서 s[i] < s[i-1]인 가장 큰 인덱스 i를 선택합니다.
2단계: i ≤ j < len(s)를 만족하면서, 범위 [i, j]에 속한 모든 k에 대해 s[k] < s[i-1]이 성립하는 가장 큰 인덱스 j를 선택합니다.
3단계: 인덱스 i-1과 j에 위치한 두 문자를 서로 교환합니다.
4단계: 인덱스 i부터 끝까지의 접미사(suffix)를 뒤집습니다.
목표는 문자열을 정렬하는 데 필요한 총 연산 횟수를 구하는 것입니다. 답이 매우 커질 수 있으므로 결과는 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"가 되어 정렬이 완료됩니다.
풀이 접근 방법
이 문제의 핵심은 각 연산이 현재 문자열을 사전순으로 바로 다음 순열로 이동시킨다는 점입니다. 즉, 정렬된 문자열에 도달할 때까지의 연산 횟수는 초기 문자열의 사전순 순위(lexicographic rank)와 같습니다. 이를 효율적으로 계산하기 위해 다음 단계를 따릅니다.
d := 크기가 26인 배열을 생성하고 모든 요소를 0으로 초기화합니다.
a := 0, t := 1로 초기화합니다.
m := 10^9 + 7 (모듈러 상수)
n := 'a'의 ASCII 코드 값
문자열 s를 뒤에서부터 순회하되, 인덱스는 1부터 시작하여 각 인덱스 i와 문자 c에 대해 다음을 수행합니다.
j := ord(c) - n (문자 c의 알파벳 인덱스)
d[j] := d[j] + 1
a := (a + sum(d[0:j]) × t // d[j]) mod m
t := t × i // d[j]
모든 순회가 끝나면 a를 반환합니다.
파이썬 구현 예시
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
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"
출력
2