1406번 - 에디터
제 부족한 실력으로는 왜 Invalid Pointer가 뜨는지 잘 모르겠습니다.
어떻게 테스트를 해봐야 할까요?
abcd문자열에서 값을 추가하고 삭제하는 정도는 문제없이 돌아갑니다
33번째 줄에서 insert 를 하고 나면 기존의 iterator 는 더 이상 사용하면 안됩니다.
대신 28번째 줄에서 했던 것 처럼 insert 함수가 반환하는 iterator 를 대신 사용해야 합니다.
이 프로그램은 이렇게 고치더라도 막상 제출하면 시간 초과를 받을 것입니다.
string 객체에서 문자열 한가운데에 문자를 삽입하거나 삭제하는 연산의 시간 복잡도는 O(n) 입니다.
그래서 다른분들은 string으로 짜시지 않았던 것이군요..
답변주신대로 insert부분 바꾸니까 런타임오류는 더이상 안뜨네요. 정말 감사합니다!!
그런데 시간복잡도가 O(N)인데 이 문제에서 시간초과가 날 것이라는걸 어떻게 아신건가요?
문자열 한 가운데에서의 string.insert, string.delete 의 시간복잡도는 문자열의 길이에 비례하며, O(n) 이라고 볼 수 있습니다.
이를 명령어의 갯수 만큼 반복하므로 O(m) 회 반복한다고 볼 수 있습니다.
따라서 이 프로그램의 전체 시간복잡도는 O(nm) 이 됩니다.
n 과 m 이 최대값일 때, 대략 10만 x 50만 = 500억 회의 연산이 필요한데, 주어진 시간 제한인 0.3 초로는 이 정도 규모의 연산을 수행할 수 없습니다.
앞으로 알고리즘의 복잡도와 제한시간도 고려하며 코드를 짜야겠네요..
자세한 설명 정말 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
choah76 2년 전
제 부족한 실력으로는 왜 Invalid Pointer가 뜨는지 잘 모르겠습니다.
어떻게 테스트를 해봐야 할까요?
abcd문자열에서 값을 추가하고 삭제하는 정도는 문제없이 돌아갑니다