시간 초과가 나는 이유는 함수의 인자로 들어가는 string s
가 함수를 호출할 때마다 복사되기 때문입니다. 이 코드에서 s
는 전혀 변경되지 않으므로, 레퍼런스 형식(string &s
)으로 전달하거나 아예 전역 변수로 놓는 등의 방법으로 개선할 수 있습니다.
14517번 - 팰린드롬 개수 구하기 (Large)
정말 너무너무 감사드립니다. 생각하지도 못한 부분 때문에 시간초과가 발생한 것이었군요.
그리고 조심스럽게 질문을 조금만 더 하겠습니다.죄송합니다.
1.일단 s를 전역으로 선언한 후에도 틀렸습니다가 나왔습니다. 10007로 나누기 때문에 오버플로 문제도 없을텐데 어느부분에서 틀렸는지 잘 모르겠습니다.
2.또한 저가 개인적으로 저 코드의 시간복잡도를 생각했을때 대략 s의 길이만큼을 두번 탐색? 하여 O(n^2) 이 되지 않을까? 라고 생각이 들긴 하는데 확실한지 모르겠습니다 ㅠㅠ
답변 다시한번 진심으로 감사드립니다.
댓글을 작성하려면 로그인해야 합니다.
gumdung 4년 전
안녕하세요.
질문을 올리기까지 정말 망설였는데 저에겐 버거운 문제라고 판단되어 이렇게 질문을 올립니다.
먼저 small 버전
https://www.acmicpc.net/problem/14505
이 문제를 풀고 나서 보고있는데 tle를 잡지를 못하고 있는 상황입니다....
저 문제도 사실 힌트를 얻어(포함배제의 원리) 간신히 풀었는데 정확한 시간 복잡도가 과연 어떻게 되는지도 모르겠더라구요.
그래서 아마 이 문제에서 tle가 발생하는 것 같은데 조금이나마 도움이 될 만한 조언들 감사히 여기겠습니다.