[C++로 풀이] 소수 찾기 (시간 초과 주의)⭐

📌 소수 찾기

난이도 ⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    vector<int> vec(n + 1);
    
    for(int i = 2; i <= n; i++)
        for(int j = i; j <= n; j += i)
            vec[j]++;
    
    for(int i = 2; i <= n; i++)
        if (vec[i] == 1)
            answer++;
    
    return answer;
}

n이 백만이 될 수도 있기 때문에 이중 for문으로 n * n 번을 돌려버리면 시간 초과 되어 버린다. for(int j = i; j <= n; j += i) 이 정도는 시간 초과 나지 않는 것같다. 수가 커질 수록 점점 텀이 넓어져서 그런지..!

배수마다 그 인덱스에 대응하는 원소를 카운팅 해준다. 1은 제외하고 2부터 돌았으니까 최종적으로 카운팅이 한번 밖에 안됐다면 나는 나의 배수에서만 해당됐다는 의미이므로 소수이다. (예를 들어 7은 7의 배수 돌 때만 딱 한번 카운팅 됐었을 것이다.)

🚀 다른 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    vector<bool> checked(n + 1, false);
    
    for(int i = 2; i <= n; i++)
    {
        if (!checked[i])
        {
            answer++;
            for(int j = 2; i * j <= n; j++)
                checked[i * j] = true;
        }
    }
    
    return answer;
}

이렇게 풀면 내 기존 풀이보다 훨씬 !! 더 시간 단축이 된다. 카운팅 하는게 아니라, 처음부터 전부 false로 초기화 해놓으므로 자기 자신을 제외하고 딱 한번이라도 자신이 다른 수의 배수에 해당되었다면 true가 되게 하여 다시는 for문을 돌며 검사하지 않도록 한다. 훨씬 효율적인 답인 것 같다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기