단어 나누기

1251번: 단어 나누기

 

나의 풀이

import sys

def seq_str(n):
    answer = []
	# 3등분 하여 뒤집고 붙이기
    for i in range(1, len(n)-1):
        a1 = n[:i][::-1]
        for j in range(i+1, len(n)):
            a2 = n[i:j][::-1]
            a3 = n[j:][::-1]
            answer.append(a1+a2+a3)
    answer.sort()
    return answer[0]

n = sys.stdin.readline().rstrip()
print(seq_str(n))

 

시간 복잡도

for i in range(1, len(n)-1) : ( 선형 시간 복잡도 )
    for j in range(i+1, len(n)) : ( 선형 시간 복잡도 )
        문자열 뒤집기 : ( 선형 시간 복잡도 )
해당 알고리즘 시간복잡도 : 삼차형 시간 복잡도 ( O(n**3) )