[Python] 백준 11656번 - 접미사 배열

문제

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

Solution

1. 인덱스 슬라이싱으로 접미사 리스트를 만든다.
2. sort() 함수를 이용하여 접미사 리스트를 정렬한다.

내 코드

# 시간 복잡도 : O(n^2)
import sys

# S = "baekjoon"
S = sys.stdin.readline().rstrip()
ans = []
for i in range(len(S)):
    ans.append(S[i:])

ans.sort()

for k in ans:
    print(k)

파이썬에는 sort() 함수와 sorted() 함수가 존재한다.

• sort() 함수는 이미 있는 리스트를 매개 변수로 입력 받아 정렬해주는 inplace 함수이다.
• sorted() 함수는 정렬하여 새로운 리스트를 만들어 던져주는 함수이다.

두 함수 모두 최악의 경우에 O(NlogN)의 시간 복잡도를 가진다고 한다.