ajax0615   7달 전

전체 문자열을 한번에 입력 받은 후, 공백을 카운트해서 공백 카운드 + 1을 출력하는 알고리즘인데요.

일반적인 경우 외에  첫 문자로 공백이 입력될 경우,  마지막 문자로 공백이 입력될 경우에는 공백을 제거한 다음 공백을 카운팅 하는 방식으로 작성하였습니다.

시간 초과가 왜 나는지 잘 모르겠어서 질문 올렸습니다!!

yukariko   7달 전

substr함수는 문자열을 자르고 복사하는 과정이들어가기때문에 선형시간이 걸립니다.

이것을 길이마다 반복하고있으니 최악의 경우 O(,^2)의 시간복잡도를 갖게 됩니다. 쉽게말해 100만 * 100만의 반복인셈이죠.

find함수를 좀 더 조사해보시면 특정 index로 부터 찾을수있는데, 이를 이용하시면 substr없이 문제를 해결할 수 있을겁니다.

ajax0615   7달 전

yukariko

substr 함수가 선형시간이 걸리는지 몰랐었네요ㅎㅎ

덕분에 코드 한줄 수정했더니 통과했습니다.

감사합니다^^

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