약 2주일간 고생한 문제다.
해법은 kmp + dp로 간단한 편이나 시간초과가 날 리가 없는 시간복잡도인데 시간초과가 나버린다.
며칠간 생각해봐도 이 이상의 풀이를 생각해내기가 불가능하다고 판단해서 풀이를 봤는데, 풀이도 똑같은 풀이를 썼다.
한 주간 이것 저것 막 해보다가 발견해낸 차이점은 각각의 index에 matching된 문자열의 길이를 vector로 관리한 코드들은 전부 시간초과가 뜨고 배열로 관리한 코드들은 전부 ac가 됐다는 점이다.
이론상 push_back의 속도는 O(1)이지만 이게 Amortized O(1)이라는 점이 중요하다. 최악의 경우에는 O(n)의 시간복잡도를 갖기 때문에 함부로 O(1)이라고 판단하면 안 된다. 그래서 검색해보니 vector의 reserve를 사용한 후 push_back을 하면 속도가 많이 줄어든다는 얘기를 듣고 reserve를 사용해서 제출해보니 ac가 떴다.
그래서, 실제로 reserve를 쓰고 난 후 push_back을 썼을 때, 그냥 push_back을 썼을 때, 그리고 배열로 관리할 때 얼마나 속도 차이가 나는가 비교해보았다.
코드
컴파일 옵션
결과
수 십번 돌려 본 후 가장 표본이라고 생각되는 결과를 뽑아보았다.
관찰 결과
1. 배열과 reserve로 미리 capacity를 확장한 후 push_back은 1.5배 차이난다.
2. 배열과 그냥 push_back은 2.5배 차이난다.
백준 문제를 풀 때에나, 최대 입력개수를 알 때에는 무조건 reserve를 한 번 해주자. 시간 내에 아슬아슬하게 들어오는 코드이거나 시간초과가 뜰 수가 없는 시간복잡도인데 시간초과가 뜰 때에는 vector을 배열로 바꿔주거나 reserve를 써주자.
