얼거스 개발 일지

---

실패한 내 코드

질문하기에서 에라토스테네스의 체를 이용하면 된다고 문제를 해결한 사람들이 작성해뒀어서 내 나름 에라토스테네스의 체를 이용해본 코드였다 🥲 이 코드로는 마지막 테스트 케이스 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