강의로 돌아가기
이영준

효율성 테스트에서 4개중 2개가 실패가 나는데 이거 이상으로는 생각이 안나네요...

include

using namespace std;

long long solution(int N) {
long long answer = 0;

vector v;

for (int i = 0; i <= N; i++) {
v.push_back(i);
}

for(int i=2;i<=N;i++){
for(int j=i*2;j<=N;j+=i){
v[j]=0;
}
if(v[i]!=0){
answer+=v[i];
}
}

return answer;
}

  • 이준혁
    배열이 0인것도 전부 체크해버려서 늦어지는건 아닐까요? 배열이 0일경우 continue로 캔슬시키시면 효율성테스트를 통과하실수 있을것같네요 이준혁 2018.09.13 21:00
1 개의 답변
어렵드아

효율성은 공간복잡도도 체크하는것으로 보입니다. i=2일때 v[i]=2 아닌가요? 초기에 v에 값을 넣을 필요는 없을듯 합니다. 그렇다면 v[j]=0 방식의 마스크를 지우지 말고 씌우는 방식으로 해보면 될듯 합니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.