실패한 내 코드
질문하기에서 에라토스테네스의 체를 이용하면 된다고 문제를 해결한 사람들이 작성해뒀어서
내 나름 에라토스테네스의 체를 이용해본 코드였다 🥲
이 코드로는 마지막 테스트 케이스 3개에서 계속 시간초과가 떠서 해결하지 못했다.
내가 생각했던 코드중에 그나마 시간 비용을 줄인 코드였어서 기록! ✏️
import java.util.ArrayList;
class Solution {
public int solution(int n) {
int answer = 0;
ArrayList<Integer> list = new ArrayList<>();
for (int i = 2; i <= n; i++) {
list.add(i);
}
for (int i = 0; i < list.size(); i++) {
int findNum = list.get(i);
int j;
for (j = 2; j < findNum; j++) {
if ( findNum % j == 0) break;
}
if (j != findNum) {
list.remove(i);
i--;
} else {
// 소수 찾음 -> 소수의 배수들 모두 제거
for (j = 2; j * findNum < list.get(list.size() - 1); j++) {
if (list.contains(j * findNum)) {
list.remove(list.indexOf(j * findNum));
}
}
}
}
answer = list.size();
return answer;
}
}- 와 사용된 메모
이 문제만 오늘 오후 7시까지 온종일 붙들고 있었는데
다른 사람 코드를 봐도 이해가 가지않아 챗GPT를 갈궈봤다.. 히히
정말 놀라운 코드가 나왔다.
챗GPT
import java.util.Arrays;
class Solution {
public int solution(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
int count = 0;
for (int i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
}내가 볼때 정말 놀라운 코드였다.
이 코드도 에라토스테네스의 체를 사용한 코드라고 한다.
공부해야지 🤓
뜯어보기
1. 사용할 변수 생성 & 초기화
-
길이가 n+1인 boolean 타입의 배열 isPrime을 만듦
-> 배열의 인덱스와 소수인지 판별할 숫자를 알아보기 쉽게 1:1로 매칭하기 위함 -
isPrime 배열을 true로 초기화함 ( 기본값 false임 )
-
소수를 카운팅 할 변수 : count
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
int count = 0;2. 2부터 i * i가 n보다 작을 때 까지 반복문 실행
반복할 내용 : 소수인지 확인해서 isPrime 배열에 반영
-> 소수가 아니면 false 처리
-> 소수가 아닌 조건 = 소수*소수
소수*소수 + 소수
소수*소수 + 소수
...for (int i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}🔻이해가 잘 안가서 진행해보았습니다 🤔 
3. 소수 개수 셈 : 2 ~ n까지 true인 값 카운팅
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
count++;
}
}🔻이해가 잘 안가서 진행해보았습니다2 🤔 
느낀점
나는 인덱스의 활용을 잘 못하는 것 같다. 🤔
처음 풀어본 날 : 23.03.24
다시 풀어본 날 : 23.03.25 ~ 28
Hello velog!