강의로 돌아가기
이영준

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

include

using namespace std;

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

vector<int> 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
  • 허진호
    for(int j=i*2;j<=N;j+=i) 여기 i*2로되어있는데 i*i 아닌가요? 허진호 2019.07.01 01:14
1 개의 답변
어렵드아

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

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