ksgkms23   2년 전

우선 제 코드입니다.

nlogn의 시간복잡도로 풀린다고 생각합니다.

lower_bound 가 이분 탐색으로 logN이 걸리고

for문으로 모든 n번 돌고있습니다.

입력값이 100,000 이고 이는 1초안에 충분히 들어와야한다고 생각이 드는데 시간초과가 뜹니다.
혹시 입력값의 범위가 100,000가 아닌가 해서 질문드립니다
혹은 제 코드가 잘못되었거나, 잘못알고있는 부분에 대한 지적을 해주시면 감사하겠습니다.

djm03178   2년 전

두 문장이 O(N)이기 때문에 총합 O(N^2)입니다.

  1. 21번째 줄, assign은 말 그대로 모든 원소를 하나씩 복사해 와서 대입합니다. 당연히 원소 수가 n개면, O(n)의 시간이 걸립니다.
  2. 22번째 줄, erase는 원하는 위치의 원소를 지운 뒤, 그 뒤쪽에 있는 모든 원소들을 전부 한 칸씩 앞으로 당겨옵니다. 평균 / 최대 O(n)개의 원소를 옮겨야 하므로 역시 O(n) 시간이 걸립니다. (다만 이 함수는 memmove를 내부적으로 사용하기 때문에 매우 빠르긴 합니다.)

ksgkms23   2년 전

assign, erase에 대한 복잡도를 모르고 그냥 쓰고 있었내요 감사합니다.

 벡터를 또 할당하는 짓을 안하고 그냥 처음 벡터만 이용해서 인덱스만 바꾸는식으로 유사하게 푸니까 시간초과안뜨고 풀게되었습니다! ^^

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