moner_ari   1년 전

만약 알고리즘을 정확하게 적용했는데도 시간 초과가 나신다면, 그건 <vector>의 한계 때문입니다.

<vector>의 erase()는 비용이 엄청납니다. erase()는 시간 복잡도가 무려 O(n)이나 되기 때문에, 적용 논리 자체는 옳더라도 시간 복잡도가 지나치게 커질 수 있습니다.

가장 앞의 element를 O(1)로 지울 수 있는 자료 구조가 어떤 게 있을지 생각하실 수 있다면, '맞았습니다!!'를 받을 수 있을 겁니다.


사실 저도 <vector>에 데여서 처음에 시간 초과가 났습니다...

여러분들은 제가 한 실수를 하지 않았으면 좋겠습니다!

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