[LeetCode] 3233. Find the Count of Numbers Which Are Not Special

문제 정의

Link : 3233. Find the Count of Numbers Which Are Not Special

You are given 2 positive integers l and r. For any number x, all positive divisors of x except x are called the proper divisors of x.

A number is called special if it has exactly 2 proper divisors. For example:

• The number 4 is special because it has proper divisors 1 and 2.

• The number 6 is not special because it has proper divisors 1, 2, and 3.

Return the count of numbers in the range [l, r] that are not special.

문제 분석

내가 이해한 문제 요약

[l,r] 범위의 수 x에 대해서 x를 제외한 2개의 수로 나누었을 때 나머지가 없는 경우를 special 하다라고 한다.

l, r 이 주어질 때 not special 한 수의 개수를 반환해라

문제를 이해해볼 때 간단한 예시는 다음과 같습니다

4일 경우, (1, 2) → special

5일 경우, (1) → not special

6일 경우, (1, 2, 3) → not special

7일 경우, (1) → not special

8일 경우, (1, 2, 4) → not special

9일 경우, (1, 3) → special

패턴 : 소수의 제곱은 special 하다

해결 방안

import kotlin.math.sqrt

class Solution {
    fun nonSpecialCount(l: Int, r: Int): Int {
        val sqrt = sqrt(r.toDouble()).toInt()
        val isPrime = BooleanArray(sqrt + 1) { true }
        isPrime[0] = false
        isPrime[1] = false

        for (i in 2..sqrt) {
            if (isPrime[i]) {
                for (j in i * 2..sqrt step i) {
                    isPrime[j] = false
                }
            }
        }

        var specialCount = 0
        for (i in 2..sqrt) {
            if (isPrime[i]) {
                val square = i * i
                if (square in l..r) {
                    specialCount++
                }
            }
        }

        return (r - l + 1) - specialCount
    }
}

문제 분석을 바탕으로 소수의 제곱이 스페셜하다라는 것을 알아냈으니 우리는 스페셜하지 않는다는 것을 다음과 같은 flow로 찾아낼 것입니다

1. 에라토네스체를 이용한 소수 찾기

2. 찾은 소수가 [l, r] 사이에 있다면, cnt +1

3. r하위에 포함되는 모든 케이스를 확인할 때까지 2 반복

4. [l, r] 개수 - 스페셜한 cnt 값 반환

느낀점

솔직히 이번 문제는 너무 어렵고 시간 제한도 빡세게 되어 있어서 도저히 다른 케이스로는 풀 수 가 없었습니다.

또한 ‘소수의 제곱만 스페셜하다’라는 명제를 항상 만족하는지 여전히 확인 및 이해하지 못해서 그냥 공식을 가져다 쓰기만 했던 것 같아서 조금 찝찝한 느낌도 있었고 실제 코딩 테스트에 나온다면 사실 틀릴 수 밖에 없다고 생각이 듭니다