문제 출처
문제 출처 : 소수 찾기
문제 이해하기
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수이다.
문제 입출력 예시를 보면 알겠지만 n까지 포함시켜야 한다.
주요 조건 이해하기 ⭐️
제한 조건을 읽지 않은 상태에서 단순히 소수를 구하는 알고리즘을 구현했을 때, 시간 초과 문제로 테스트를 통과하지 못하는 경우가 발생할 것이다.
바로 아래 코드가 시간 초과로 인해 테스트를 통과하지 못한 코드이다.
class Solution {
public boolean isPrime(int n) {
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public int solution(int n) {
int answer = 0;
for (int i = 2; i <= n; i++) {
if(isPrime(i)) {
answer++;
}
}
return answer;
}
}
다시 문제에서 주어진 제한 조건을 읽어보면 n은 최대 1,000,000 까지 올 수 있고, 소수 판별 부분을 isPrime 함수로 별도로 분리했을 뿐이지 사실상 2중 for문으로 구현한것과 동일하며 이 로직의 시간 복잡도는 O(n^2) 이므로 1초를 초과하게 된다.
대부분 이러한 이유로 틀렸을 확률이 높다(필자 포함). 그 이유는 '질문하기' 탭만 가도 알 수 있다.
관련된 내용을 구글링을 통해 찾아본 결과 에라토스테네스의 체의 개념을 적용하면 이 문제를 풀 수 있었다.
에라토스테네스의 체에 대한 설명은 나동빈님의 유튜브 영상에 잘 설명되어 있다.
24강 - 에라토스테네스의 체 [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #24 ]
언제 사용할까? 🧐
한 두개의 숫자를 가지고 소수를 판별할 땐 위와 같은 방법으로 풀어도 문제는 없으나, 대량의 숫자를 가지고 소수를 한꺼번에 판별하고자 할 때 에라토스테네스의 체를 사용하는 것이 좋다.
-
가장 먼저 소수를 판별할 범위만큼 배열을 할당한 후 그 인덱스에 해당하는 값을 넣어준다.
(나동빈님에서 이론 설명할 땐 2차원 배열을 생성하지만, 실제 코드는 1차원 배열이다) -
2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다. (이때 자기 자신 즉 2는 지우지 않는다.)
-
이제 3의 배수를 지운다 (마찬가지로 자기 자신인 3을 지우지 않는다.)
-
만약 이미 지워진 숫자인 경우는 건너 뛴다.
-
2 ~ 4의 과정을 반복한다.
에라토스테네스의 체를 실제 코드로 옮기고, 이를 바탕으로 제출한 코드를 작성해보았다.
제출 코드
class Solution {
public int solution(int n) {
int[] prime = new int[n + 1];
int answer = 0;
//소수가 아니라면 0, 0과 1은 소수가 아니므로 0
prime[0] = prime[1] = 0;
for(int i = 2; i <=n; i++) prime[i] = i; //2부터 소수를 구하고자 하는 구간의 모든 수 나열
for(int i = 2; i < n;i++){
if(prime[i] == 0) continue; //소수가 아니라면 continue
for(int j = 2*i; j <=n; j+=i) prime[j] = 0; //소수의 배수는 소수를 약수로 가지므로 제외
}
//소수 개수 구하기
for(int i = 0; i <prime.length; i++)
if (prime[i] != 0) answer++;
return answer;
}
}