⚠️JAVA 언어를 사용합니다.
소수 문제.. 너무 어렵다
🔒문제
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
- n은 2이상 1000000이하의 자연수입니다.
🗝️정답
import java.util.Set;
import java.util.HashSet;
class Solution {
public int solution(int n) {
//1. 선언 및 초기화
Set<Integer> set = new HashSet<> ();
set.add(2);
for(int i=3; i<=n; i+=2){
set.add(i);
}
//2. n<9 일때 처리
if(n<9) return set.size();
//3. 소수가 아닌 수 제거
for(int i=3; i<n; i++){
if(set.contains(i)){
for(int j=i+i; j<=n; j+=i){
set.remove(j);
}
}
}
return set.size();
}
}
💡풀이해석
- 1부터 주어진 n까지의 숫자 중에 소수의 갯수를 세는 문제. 이때 1은 소수가 아니므로 미리 제외한다.
- 에라토스테네스의 체 방식을 사용한다. 2부터 n까지 모든 수를 Set에 미리 넣은 후 소수가 아닌 수를 제거한다. 이때 (2를 제외한)짝수는 항상 소수가 아니므로 2와 홀수만 Set에 저장한다.
- 소수가 아닌 수를 제거할 때는 3부터 n-1까지 반복하며 배수를 제거한다.
// 1. 선언 및 초기화(기초 작업)
- Set<Integer> set : 전체 수를 담을 Set 생성
- set.add(2) : 주어지는 n이 2이상이므로 2는 항상 포함된다. 다음 반복문 때문에 미리 따로 넣어준다.
- for(int i=3; i<=n; i+=2) : 3부터 시작하여 홀수만 저장
// 2. n<9 일 때 처리
- if(n<9) return set.size() : 주어진 수가 9미만이면 모든 홀수가 3 이상으로 나눠지지 않으므로 추가작업이 필요하지 않다. 따라서 바로 set의 길이 리턴
// 3. 소수가 아닌 수 제거
- for(int i=3; i<n; i++) : 3이후부터 하나씩 증가하며 배수를 제거한다.
- if(set.contains(i)) : 현재 i보다 작은 수의 배수로 미리 지워졌을 수도 있으니, 지워지지 않고 set에 있는 수만 제거 과정을 수행한다.
- for(int j=i+i; j<=n; j+=i) : n보다 작을 때까지 i의 배수를 구해서 set에 포함되어 있으면 삭제한다.
//반환
- return set.size() : 소수인 수만 set에 저장되어 있으므로 set의 size가 곧 소수의 갯수이다.
에라토스테네스의 체
1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.
3. 2부터 시작하여 남아있는 수를 모두 출력한다.
✏️자기 분석
위 답은 아마 두 번째 풀이일 것이다. 빨리 푼 것처럼 보이나, 감을 못 잡아서 답을 내기까지 2시간이 넘게 걸렸다(아마도).
이것저것 많이 찾아 본 탓도 있고, 그 찾아본 내용들이 거의 비슷했으나 이해하지 못해서 계속 빙빙 돈 탓도 있다.
첫 번째 풀이
import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;
class Solution {
public int solution(int n) {
int j = 0;
boolean key;
Set<Integer> set = new HashSet<> ();
set.add(2);
for(int i=3; i<=n; i++){
key = true;
Iterator<Integer> it = set.iterator();
while (it.hasNext()){
if(i%it.next() == 0){
key = false;
break;
}
}
if(key) set.add(i);
}
return set.size();
}
}첫 번째 풀이는 오직 감으로만 풀었다. '이터레이터를 어떻게 썼더라..' 정도만 찾아봤다.
소수인 수만 판별하여 Set에 저장하려고 하였다. 3부터 n까지 하나씩 증가하며 그 수가 set에 저장된 소수 중 하나라도 나누어지지 않아야 set에 추가하는 방식으로 하였다. 때문에 반복문을 돌 때마다 iterator를 새로 생성해야했다.
이렇게 하면 모든 수를 그 수보다 작은 모든 수로 나누어 보지 않아도 될 것이라 생각해서 시간을 아낄 수 있을 줄 알았다.
하지만, 어쨋든 2부터 n까지의 모든 수를 이중 반복해야 했으니 시간초과로 실패했다.
심지어 효율성 테스트는 너무 오래걸려서 내가 멈췄다.
두 번째 풀이
위 정답이 된 풀이이다. 이것도 시간복잡도가 좋진 않아서 실패할까봐 걱정했다. 다행히 성공이었다.
첫 시도를 실패하고 소수 판별 알고리즘을 구글링했다. 아까는 여기까지만 했다.
세 번째 풀이
이건 방금 포스팅 하면서 생각난 것이다.
아까 문제를 풀면서 "특정 숫자의 제곱근 까지만 소수를 판별하면 된다"라는 것을 알게 되었는데, 잘 이해도 안되고 내 풀이에 적용할 수 없을 것 같아서 넘어갔는데, 지금 생각해보니 두 번째 풀이의 for문에 적용해도 괜찮을 것 같다.
채점 결과 거의 차이가 없다.
n번째 까지 반복하며 배수를 찾는 것보다 n의 제곱근 까지만 반복하면 범위가 더 적어져서 빠를 줄 알았다.
하지만 앞선 방법으로 했을 때, 제곱근 보다 넘어가는 수가 i로 주어져도 if문을 만나 반복문을 바로 통과하기 때문에 큰 차이가 없는 것으로 보인다. 그래도 시도는 좋았다.
🚩결론
1. Lv.1이 끝나면 알고리즘을 먼저 공부한 후에 시작하자. 무지성으로 뇌피셜로만 풀려니 효율성이 떨어진다.
2. 수학이 너무 약한 것 같다. 이거는... 수학공부를 다시 할 순 없고, 자주 나오는 문제 유형의 알고리즘을 외우자.
3. 포스팅하면서도 아까는 생각하지 못한 새로운 풀이가 생각나서 좋다. 생각에서 멈추지 않고 시도해 본 것도 굿
