yoo4471   4년 전

[1,2,3,4]를 입력받고 숫자 1, 2, 3, 4를 얻기 위해 stoi() 와 string::substr() 를 사용했습니다.

그리고 시간 초과가 발생했습니다.

string::substr()는 주어진 스트링 길이만큼 복사해서 새로운 스트링을 만들기 때문에

< n = 숫자 갯수, k = substr()의 길이 > 일 때

제가 짠 코드는 O(n*k) 가 되지 않나 생각합니다.

string substr (size_t pos = 0, size_t len = npos) const;


djm03178   4년 전

substr에 인자를 하나 주면, 그 지점부터 문자열의 끝까지를 반환하지 않던가요? 그러면 O(len*n)이 될 것 같은데요.

yoo4471   4년 전

제가 입력받은 문자열의 전체 길이를 len으로 사용하고 있어서 k를 따로 썼네요.

말씀하신게 맞습니다.

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