1) SortCharacters 수도코드 및 시간 복잡도
앞서서 살펴본 sortcharacters (문자열 내 존재하는 글자들을 정렬하는) 함수의 전체 수도코드 및 시간 복잡도는 다음과 같습니다.
2) ComputeCharClasses(S,order)
다음으로 computecharclasses 함수는 문자열 내 존재하는 글자들을 분류하는 함수입니다.
s=ababaa$ 에서는 총 분류할 범주가 3개입니다. (서로 다른 글자가 세 개 이므로) ; a b $
따라서 숫자로 표현하면 모든 글자는 0,1,2 3개의 범주 중 하나에 속하게 됩니다.
1) class <- array of size s
우선 class 라는 배열을 만들어줍니다. 이 배열에 문자열의 범주를 분류해줄 것입니다.
class 는 전체 문자열 크기만큼의 공간을 가져야하므로,
class = [⬜️,⬜️,⬜️,⬜️,⬜️,⬜️,⬜️] 이 빈 7개의 박스를 차차 채워주면 될 것입니다. 실제 코드 작성에서는 그냥 리스트 만들어놓고 append로 추가하면 될 것 같습니다.
2) class[order[0]] <-0
앞서 sortcharacters 를 통해 order=[6,0,2,4,5,1,3] 이 반환되었습니다. (= $aaaabb)
order[0]=s[6]=’$’ 입니다. 지금 처음 분류를 시작하는 것이니까 맨 처음 등장한 글자 $는 0범주에 속합니다. 그리고 특수기호는 전체 문자열에서 딱 한 개이므로 0도 다시 등장하지 않을 것입니다.
class = [⬜️,⬜️,⬜️,⬜️,⬜️,⬜️,0]
3) for i from 1 to (size s) - 1 :
if s[order[i]] != s[order[i-1]]:
class[order[i]]=class[order[i-1]]+1 else:
class[order[i]]=class[order[i-1]]
그 후부턴 바로 이전의 알파벳과 글자가 같으면 이전 알파벳의 클래스를 그대로 넣어주고 아니면 1씩 늘려줌으로써 분류를 합니다.
Order[1] =s[0]=a , != ‘$’ 이므로 이제부터 a 알파벳들은 0 + 1 = 1번 범주에 속하게 됩니다.
class = [1,⬜️,⬜️,⬜️,⬜️,⬜️,0]
order[2], order[3] 쭉쭉쭉 분류를 하며 한번도 등장하지 않은 알파벳 글자가 나올 경우는 +1 을 하여 새로운 범주에 배정해줄 것입니다.
최종 class 는 [1,2,1,2,1,1,0] 이 됩니다.
가능한 이유,전체 수도코드,시간복잡도
order 은 sortcharacters 함수에 의해 문자열을 오름차순으로 순차적으로 정렬한 후 인덱스를 반환한 것이기 때문에 제일 작은 글자부터 순차적으로 등장합니다. 그렇기 때문에 새로운 알파벳은 이전 알파벳 글자들의 인덱스가 다 끝난 후에야만 순차적으로 등장할 수 있습니다. 바로 이전 알파벳의 범주와만 비교해주는 computecharclasses 는 그래서 작동이 가능합니다.
전체 수도코드와 시간복잡도는 다음과 같습니다.
