성능 요약
-
메모리: 52.4 MB, 시간: 202.81 ms - Answer Code1(2023.02.20)
-
메모리: 56 MB, 시간: 17.91 ms - Answer Code2(2023.02.24)
구분
- 코딩테스트 연습 > 연습문제
Answer Code1(2023.02.20)
class Solution {
public int solution(int n) {
boolean flag; // 소수이면 true, 아니면 false
int answer = 0;
//에라토스테네스의 법칙
for(int i = 2; i <= n; i++) {
flag = true;
for(int j = 2; j <= Math.sqrt(i); j++) {
if(i%j == 0) {
flag = false;
break;
}
}
// flag = true, 소수값이므로 +1 추가
if(flag == true) {
answer++;
}
}
return answer;
}
}
Answer Code2(2023.02.24)
class Solution {
public int solution(int n) {
int answer = 0;
int[] arr = new int[n + 1];
for (int i = 2; i <= (int) Math.sqrt(n); ++i) {
if (arr[i] == 1) continue;
for (int j = i + i; j <= n; j += i) {
arr[j] = 1;
}
}
for (int i = 2; i < arr.length; ++i) {
if (arr[i] != 1) ++answer;
}
return answer;
}
}
문제 풀이
-
첫 번째 풀이는 시간이 너무 걸리고 효율성 테스트가 너무 높게 나와서, 해당 문제점을 개선하기 위해 다시 풀었다.
-
두 번째 풀이의 아이디어는 밈아님의 소수찾기 풀이방법를 통해 알 수 있었다. (밈아님 감사합니다)
-
[1] 입력 받는 n 값이 커질 수록 반복문이 도는 횟수도 더 많아지므로, 반복문을 n번 돌리는 것이 아닌 n의 제곱근번을 돌리게 하여 반복문 실행 횟수를 줄이도록 했다.
- 반복문을 n 까지가 아닌 n의 제곱근까지만 검사해도 소수인지 판별이 가능했다는 것이다.
-
[2] 그리고 첫 번째 풀이 방법에서 n번 반복되는 코드와 달리 두 번째 풀이 방법에는 소수의 개수를 체크하는 for문을 따로 빼냈다.
- 굳이 n의 제곱근번을 반복하지 않고, 해당 배열의 갯수만큼 반복해도 소수가 몇개인지 확인할 수 있기 때문이다.
Review
-
이번 문제는 성능 개선과 더불어, 소수 찾기에 대한 문제 풀이를 깊게 공부하게 된 점이 인상깊어서 정리했다.