[Leet Code] Count Primes

안녕하세요 :)
오늘은 5월 2주차 3번째 알고리즘! Count Primes 풀이를 적어보겠습니다.

---

문제

요약
n 까지의 수 중에서 소수의 개수를 return 하는 문제입니다.

TMI
사실, 범위를 주고 소수의 개수를 구하는 문제들은 흔하고 쉬운 알고리즘에 속합니다.
저 또한 다른 사이트에서 적-당히 효율적으로 풀어서 통과한 문제들이 많아요!

사담이긴 하지만 이 흔한 소수의 개수 구하기 문제를 Leet Code에서 풀면서 많은 사람들이 Leet Code로 알고리즘을 공부했으면 좋겠다는 생각이 마구마구 들었습니다.
제가 진행하고 있는 챌린지의 경우에는 (태평양시 기준으로) 24시간이 끝나면 솔루션이 주어집니다.
말 그대로 답지를 볼 수 있는 것이죠.
근데 답지를 그냥 보는 것이 아닌, 상세한 설명과 함께 주어집니다. 물론 안보고 푸는게 제일 베스트일 것입니다.
하지만, 저는 아직 공부하는 중이어서 그런지 한번에 accept 를 받은 적은 없습니다.. 그렇다고 답지를 보기엔 너무 .. 노력을 안하는 것 같고..
그래서 있는 것이 힌트들인데, 단계별로 생각해볼만한 것들이 힌트로 간략하게 적혀있어서 힌트를 보고 많이 생각을 해보고 알고리즘을 다시 짜기도 합니다.

이렇게 힌트를 하나씩 보면서 로직을 구상하는 능력을 키울 수 있을 것 같아요.
그래서 모두한테 알고리즘을 공부할 때는 Leet Code로 하라고 동네방네 소문내고 싶은 애정가는 사이트입니다..

여기까지는 제 사담이었고, 코드 설명을 밑에 적어보겠습니다.

처음 시도한 방법

정말 간단하게, n번의 루프를 돌면서 소수의 개수를 더해주었습니다.
역시나, Time 에러를 마주쳤습니다..

두번째로 시도한 방법

힌트를 참고해서, 소수를 구할 때마다 배열에 담았습니다.
그리고 루프를 돌면서 만약 해당 값이 소수 배열의 수로 나눠지는 경우를 분기처리해주었습니다.
이 방법도 n의 제한이 5*10^6 이라는 큰 수여서인지 Time 에러가 발생했습니다.

힌트를 참고해서 시도한 마지막 방법

힌트를 보니까, 루프의 조건을 i * i < n 으로 설정하라는 조언이 있었습니다.
그것을 보고 for문의 조건을 바꾸어서 반복 횟수를 줄여주고, bfs/dfs 알고리즘을 참고해서 소수를 하나 구하면, 그것의 배수들을 모두 조건에서 제외해주었습니다.
이렇게 풀고 나니 accept를 받을 수 있었습니다!

코드 설명

boolean[] isPrime = new boolean[n];
int result = 0;

isPrime 은 n 개의 수에 대한 소수 여부입니다.
소수를 구했을 경우는, 그 값의 배수들을 isPrime 에서 false 처리를 해주었습니다.
result 는 소수의 개수를 체크하는 변수입니다.

for (int i = 2; i < n; i++) {
    isPrime[i] = true;
}

위의 코드는 isPrime 을 true 로 초기화하는 코드입니다.
사실, 초기화 작업이 필요없을 것 같았지만 루프의 조건이 i * i 인 만큼 false 상태의 소수가 발생할 수 있습니다.
그래서 초기화를 꼭 진행해주어야합니다.
ex) 3은 소수지만, i가 2부터 시작할 경우 2 * 2 < 3 이 성립하지 않기 때문에 for문을 순회할 수 없습니다. 그래서 미리 true 로 초기화해야 합니다.

for (int i = 2; i * i < n; i++) {
    if (!isPrime[i]) continue;
    for (int j = i * i; j < n; j += i) {
        isPrime[j] = false;
    }
}

for루프는 소수가 아닌 것을 찾아서 false 처리를 해주는 로직입니다.
따라서 이미 소수가 아니라고 체크된 것은 제외해주고 소수라면, 그 배수들을 false 로 처리합니다.
여기까지 생각하셨다면, 진짜 다 푸신 겁니다.

for (int i = 2; i < n; i++) {
    if (isPrime[i]) result++;
}

이제 true 로 설정된 소수들의 개수를 세서 return 합니다.

전체 코드

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        int result = 0;

        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i * i < n; i++) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }

        for (int i = 2; i < n; i++) {
            if (isPrime[i]) result++;
        }

        return result;
    }
}

---

마무리

간단하게 조건을 줄여나가면서 효율성을 잡을 수 있었던 코드입니다.
이렇게 풀고 나니까 알고리즘이 더 재밌어지는데 .. 제 적성은 역시 개발인가봅니다.
저는 인스타 스토리에 Leet Code로 알고리즘 공부하라고 또 영업글을 올리러 가보겠습니다 :)

이번 포스팅도 읽어주셔서 감사합니다!