heus   2년 전

될 줄 알았는데 한 50퍼정도 되면 시간초과가 뜨는데 시간 잡아먹을게 슬라이싱 밖에 없어서요 ㅠ

bupjae   2년 전

python 의 슬라이싱은 매번 새로운 객체를 만들어내는 O(n) 연산입니다.

따라서 이 프로그램의 전체 시간복잡도는 O(n^2) 이 됩니다.

heus   2년 전

정답 코드에서는 아래와 같이 처리하는데 이는 새로운 생성이 아니라 데이터 범위만 지정하는 개념이라 시간 소요가 다른가요?

if stack[-len(b):] == b:
    del stack[-len(b):]

bupjae   2년 전

del 은 새로운 객체를 만들지 않고, 이미 있는 객체의 내용을 바꾸는 연산입니다.

python 의 문자열은 immutable 이므로 del 연산을 사용할 수 없습니다.

정답 코드는 stack 가 list 일 겁니다.

heus   2년 전

감사합니다

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