9935번 - 문자열 폭발
될 줄 알았는데 한 50퍼정도 되면 시간초과가 뜨는데 시간 잡아먹을게 슬라이싱 밖에 없어서요 ㅠ
python 의 슬라이싱은 매번 새로운 객체를 만들어내는 O(n) 연산입니다.
따라서 이 프로그램의 전체 시간복잡도는 O(n^2) 이 됩니다.
정답 코드에서는 아래와 같이 처리하는데 이는 새로운 생성이 아니라 데이터 범위만 지정하는 개념이라 시간 소요가 다른가요?
if stack[-len(b):] == b: del stack[-len(b):]
del 은 새로운 객체를 만들지 않고, 이미 있는 객체의 내용을 바꾸는 연산입니다.
python 의 문자열은 immutable 이므로 del 연산을 사용할 수 없습니다.
정답 코드는 stack 가 list 일 겁니다.
감사합니다
댓글을 작성하려면 로그인해야 합니다.
heus 2년 전 1
될 줄 알았는데 한 50퍼정도 되면 시간초과가 뜨는데 시간 잡아먹을게 슬라이싱 밖에 없어서요 ㅠ