snrnsidy   5년 전

이 알고리즘의 시간복잡도는 O(l) (l은 주어진 문자열의 길이)이고 l=500000이여서 시간초과가 뜨지 않을 거라고 생각이 드는데 계속 시간 초과가 나오네요.

혹시 string에서의 + 연산자의 시간복잡도가 O(1)이 아닌건가요??

jung2381187   5년 전

두 문자열을 이어붙이려면 뒤쪽 문자열에 있는 문자를 하나씩 모두 앞쪽 문자열에 가져와야 하니 시간 복잡도가 O(l)입니다.

snrnsidy   5년 전

감사합니다!

댓글을 작성하려면 로그인해야 합니다.