jjjooo48   1년 전

문제가 뭔지 알려주세요. 

분명 테스트케이스를 계속 돌려도 다 성공이던데, 왜 채점시스템에서는 '틀렸습니다'가 뜰까요?

런타임에러도.. 메모리 초과도...아닌 정말 반례가 있는 걸까요..

몇시간째 붙잡고 있다가 글 올립니다.

dh0450   1년 전

단어의 길이는 1,000,000을 넘지 않는다.

arr 배열 길이를 늘려주세요

jjjooo48   1년 전

감사합니다 ! 

그런 이유가 있었군요!

+ 시간초과 문제 해결을 위해 int len=strlen(str); 처리 해주었습니다.

근데 왜 이렇게 코드를 작성하면 시간복잡도가 줄어드는 건가요?

dh0450   1년 전

for(A; B; C) {D} 는 처음 A 식을 수행하고 

B가 참인지 파악하고 D 를 수행한 하고 C 를 수행 후 다시 B가 참인지 평가하는 루틴을 반복합니다.

이때 B 가 함수라면 함수를 매번 호출하게 되는데, 문자열 길이를 파악하는 strlen() 은 시간복잡도가 아마 O(N) 으로 보입니다.

그래서 기존코드는 시간복잡도가 O(N^2) 가 됩니다.

jjjooo48   1년 전

감사합니다! 많이 알아가네요  ㅎㅎ

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