[JAVA] 백준 #1016 제곱ㄴㄴ수 | 에라토스테네스의 체 알고리즘 | 시간 초과 해결 방법

[JAVA] 백준 #1016 제곱ㄴㄴ수

1016번: 제곱 ㄴㄴ 수

 

🔒 문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

 

⌨️ 입력

첫째 줄에 두 정수 min과 max가 주어진다.

 

🖥️ 출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

 

⚠️ 제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

---

 

우선 문제 지문 자체가 단순해서 구현 과정에서 어려움은 전혀 없었다. 하지만 그냥 단순하게 직관적으로 for문을 구성하면 시간초과가 발생한다. 그래서 이를 해결한 방법과 새로 학습한 알고리즘 '에라토스테네스의 체' 알고리즘을 기록해보고자 한다. 

 

우선 제한에서 min과 max 값이 무지막지하게 크다고 조건을 제시했으므로, 두 변수의 자료형은 고를 때 integer가 아닌 long을 사용해야 한다.

정수형 타입	할당되는 메모리 크기	데이터 표현 범위
int	4 byte	-2,147,483,648 ~ 2,147,483,647
long	8 byte	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

 

 

🔹 1차 시도 ( 시간 초과 오답 )

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        long min = Long.parseLong(st.nextToken());
        long max = Long.parseLong(st.nextToken());
        int count = 0;
        
        /********** 제곱수 찾기 ************/
        for( long i = min; i <= max; i++ ){
            boolean divided = false;

            for( long j = 2; j * j <= max ; j++ ){
                if( i % ( j * j ) == 0 ){
                    divided = true;
                    break;
                }

            }
            if(!divided) count++;
        }
        /*******************************/

        System.out.println(count);

    }
}

 

우선 첫 시도는 직관적으로 문제를 보자마자 구성한 풀이이다. 최솟값부터 최댓값까지 반복문을 돌면서 2의 제곱, 3의 제곱, ...... max^(1/2)의 제곱까지 순회하면서 나누어 떨어지면 break, 그렇지 않으면 count ++ 이런 식으로 직관적인 코드를 구성했다. 주어진 테스트케이스에 대해서는 올바른 정답을 출력했지만 막상 제출하고 보니 시간 초과가 발생했다. 시간 복잡도는 O(M^(3/2))이다.

 

주어진 예제 중에 min = 1, max = 1000 일 때 제곱ㄴㄴ수는 총 608개이다. 1 이상 1000 이하의 1000개의 수 중 60% 이상이 제곱ㄴㄴ수이다. 그러니까 단순히 말하면 제곱ㄴㄴ수보다 제곱수로 나뉘는 수가 더 적다는 것이다. 그럼 제곱ㄴㄴ수를 찾는 것보다 제곱ㄴㄴ수가 아닌 수, 즉 제곱수로 나뉘는 수를 찾는 게 훨씬 효율적이라는 의미!

---

에라토스테네스의 체 알고리즘

이를 찾아내는 알고리즘이 바로 에라토스테네스의 체 알고리즘이다.

[ 에라토스테네스의 체 알고리즘]이란 고대 그리스 수학자 에라토스테네스가 발견한 것으로 수학에서 소수를 찾는 빠르고 쉬운 방법이다. 

출처: 에라토스테네스의 체 위키백과

 

1. 범위 안에 있는 모든 수를 나열하고(예시에서는 2부터 120)

2. 우선 2는 소수이므로 소수로 입력해 두고, 2의 배수를 모두 찾아서 소거한다.

3. 남아있는 수 중 첫 번째인 3을 소수로 입력해 두고, 3의 배수를 모두 찾아 소거한다.

4. 그다음 남아있는 수 가운데 5를 소수로 입력해 두고, 5의 배수를 모두 찾아 소거한다.

...

이런 식으로 체를 만들고 거기서 조건에 해당하지 않는 수를 모두 찾아 제거한 뒤 걸러져서 남은 수가 바로 조건에 해당하는 소수인 것이다. 

 

우린 이 알고리즘을 소수 찾기가 아닌 제곱ㄴㄴ수 찾기에 사용할 것이다. 

 

 

🔹에라토스테네스의 체 알고리즘 구현부

 

	static boolean[] sieve; // 에라토스테네스의 체
	static long min;
	static long max;
    
    	..[ 중간 생략 ]..

	public static void Eratos(){
        for( long i = 2; i * i <= max; i++ ){
            long pow = i * i;

            long initial = ( min % pow == 0 ) ? min / pow : ( min / pow ) + 1 ;

            for( long j = initial; pow * j <= max; j++ ){
                sieve[(int)( pow * j - min )] = true;
            }
        }
 	}

 

우선 우리에게는 제곱ㄴㄴ수만 거를 수 있는 거름망 '에라토스테네스의 체'가 필요하다. 그 역할을 해줄 체가 바로 boolean 타입의 배열 sieve이다. sieve의 크기는 min 이상, max 이하의 범위를 모두 포함해야 하므로 사이즈를 'max - min + 1'로 할당해 준다.

 

우리는 Eratos() 함수에서 제곱ㄴㄴ수가 아닌 수들을 찾아내 거름망(sieve)에 true로 표시할 것이다. 그럼 제곱ㄴㄴ수가 아닌 수는 뭘까?

제곱ㄴㄴ수가 아닌 수는 바로 ' 제곱수와 그 제곱수의 배수들 '이다

 

자 뭘 찾을지 정확히 알았으니 이제 Eratos() 함수를 만들어보자. 에라토스 함수는 두 개의 for문으로 구성되어 있다. 

첫 번째 가장 바깥을 감싸고 있는 for문은 2부터 max의 제곱근까지 순회하며 제곱수 pow를 구한다. 

그러니까 i는 2, 3, 4, 5 ... max^(1/2)까지 증가하고 각 i의 제곱수인 pow는 4, 9, 16, 25 ... max까지 증가한다.

 

그럼 두 번째 for문을 만들건데 여기서 조금 헷갈리는 부분이 등장한다. 두 번째 for문의 초기값을 뭘로 설정해야 할까? 

예를 들어 min값이 10,000일 때 만약 그냥 j = 1부터 시작한다면 j = 2499까지 범위 내에 있지도 않은 모든 4의 배수를 하나하나 순회해야 한다. 변수 값의 크기가 꽤 크기 때문에 효율성을 따져보면 초기값을 min 값에 맞춰서 설정하도록 하자.

 

long initial = ( min % pow == 0 ) ? min / pow : ( min / pow ) + 1 ;

 

그러므로 초기값은 범위의 최솟값인 min과 나눴을 때 나누어 떨어지면 그 값부터, 나누어 떨어지지 않는다면 +1 한 값부터 시작한다. 예를 들어 min값이 10,000이면 초기값은 2500 ( 4 * 2500 = 10,000 ), min이 10,001이라면 초기값은 2501( 4 * 2501 = 10,004 )부터로 설정하는 것이다. 

 

그다음엔 max보다 작은 제곱수의 배수들을 찾아서 sieve 배열에 표시해 둔다. 이때 배열의 인덱스는 0부터 max - min까지이므로 현재 찾은 제곱수의 배수의 인덱스는 ( 제곱수의 배수 - min )과 같다. 그럼 이렇게 제곱ㅇㅇ수를 찾아서 걸러냈으니 체에 남은 것은 우리가 찾는 제곱ㄴㄴ수이다. 

 

전체 코드는 아래에서 확인할 수 있다.

 

 

🔐 전체 코드 

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static boolean[] sieve; // 에라토스테네스의 체
    static long min;
    static long max;


    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        min = Long.parseLong(st.nextToken());
        max = Long.parseLong(st.nextToken());
        
        sieve = new boolean[ (int)( max - min + 1 ) ]; 
        int count = 0;

        Eratos();

        for( int i = 0; i < sieve.length; i++ ){
            if( !sieve[i] ) count++;
        }
        System.out.println(count);

    }

    public static void Eratos(){
        for( long i = 2; i * i <= max; i++ ){
            long pow = i * i;

            long initial = ( min % pow == 0 ) ? min / pow : ( min / pow ) + 1 ;

            for( long j = initial; pow * j <= max; j++ ){
                sieve[(int)( pow * j - min )] = true;
            }
        }
    }
}

 

 

- 참고한 블로그

[백준 / JAVA] 백준 알고리즘 1016번 제곱 ㄴㄴ수 - 𝝅번째 알파카의 개발 낙서장