[JAVA][Baekjoon] 1016번 제곱 ㄴㄴ 수 🌟🌟🌟🌟

https://www.acmicpc.net/problem/1016

📌 접근 방식

1️⃣ 제곱수의 범위 설정:

• min과 max가 주어지면, 제곱ㄴㄴ수는 1보다 큰 제곱수로 나누어지지 않는 수입니다. 이 말은 곧 2의 제곱, 3의 제곱, 4의 제곱 등 여러 제곱수로 나누어지지 않는 수를 찾아야 한다는 뜻입니다.
• 제곱수는 i * i 형태로 구할 수 있는데, i는 2부터 시작해서 i * i가 max 이하인 값을 찾으면 됩니다.

2️⃣ 배수 마킹 방식:

• 이 문제는 범위 내에서 제곱수의 배수를 제외하는 방식으로 해결할 수 있습니다. 예를 들어, 제곱수가 4(2의 제곱)라면, 4, 8, 12, 16, 20, ...처럼 제곱수의 배수를 모두 제외해야 합니다.
• 이를 효율적으로 처리하기 위해, 주어진 범위 [min, max]에 대해 배열 check를 만들어 배수들을 true로 마킹해 줍니다.

3️⃣ 배수 처리:

• min과 max가 주어지면, min 이상 max 이하 범위의 수에 대해 제곱수의 배수를 마킹합니다. i * i로 시작하여 그 배수들을 check 배열에 true로 표시합니다.

4️⃣결과 출력:

• 최종적으로 check 배열에서 false인 값들의 개수를 세면, 그것이 바로 제곱ㄴㄴ수의 개수가 됩니다.

 

✅ PASS CODE

import java.io.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        // 입력 받기
        long min = sc.nextLong();
        long max = sc.nextLong();

        // 제곱수의 배수를 마킹할 배열 선언
        boolean[] check = new boolean[(int)(max - min + 1)];

        // 2부터 시작해서 제곱수로 나누어지는 값을 마킹
        for(long i=2; i*i <= max; i++){
            long pow = i*i;
            long start_index = min/pow;

            // 시작 위치 계산
            if(min % pow != 0) {
                start_index ++;
            }

            // 제곱수 배수들 마킹
            for(long j = start_index; pow * j <= max; j++){
                check[(int) ((j * pow) - min)] = true;
            }
        }
        
        // 제곱ㄴㄴ수의 개수 세기
        int count = 0;
        for(int i=0; i<=max-min; i++) {
            if(!check[i]) {
                count++;
            }
        }
        System.out.println(count);
    }
}

 

1️⃣ 입력 처리 및 check 배열 초기화

1. min과 max 값을 입력받는다. 주어진 범위 [min, max] 내에서 제곱ㄴㄴ수를 찾는다.
2. check 배열은 min과 max의 차이에 맞는 크기로 선언된다. 이 배열은 범위 내의 각 숫자가 제곱수의 배수인지 아닌지를 확인하는 데 사용됩니다. 배열의 크기는 max - min + 1로 설정되며, 이 배열에서 각 인덱스는 min부터 max까지의 값을 나타낸다.
   예를 들어, check[0]은 min, check[1]은 min + 1을 의미합니다.

2️⃣ 2부터 시작해서 제곱수를 계산하고 그 배수의 시작 인덱스를 구하기

1. for 루프는 i를 2부터 시작하여 i * i (즉, 제곱수)를 계산합니다. 루프는 i * i <= max 조건을 만족하는 동안 계속 실행된다.
   즉, i가 커질수록 i * i가 max보다 커지면 종료된다.
2. pow = i * i;는 제곱수를 계산한다.
   예를 들어, i = 2이면 pow = 4, i = 3이면 pow = 9처럼 계산된다.
3. start_index = min / pow;는 min에서 제곱수 pow로 나누었을 때, 가장 작은 배수의 인덱스를 찾는다.
   예를 들어, min = 10이고 pow = 4이면 start_index = 10 / 4 = 2가 된다. 즉, 제곱수 4의 배수는 4 * 2 = 8부터 시작한다.

3️⃣ 배수의 시작 인덱스 조정

1. if (min % pow != 0)는 min이 pow로 나누어지지 않는다면, 즉 min이 pow의 배수가 아니라면, 시작 인덱스를 한 칸 증가시킨다.
   예를 들어, min = 10, pow = 4인 경우, 10 % 4 != 0이므로 start_index는 2에서 1을 증가시켜 3이 된다. 즉, 4 * 3 = 12부터 배수를 마킹한다.

4️⃣ 제곱수의 배수 마킹

1. for (long j = start_index; pow * j <= max; j++)는 start_index부터 시작하여 pow * j가 max 이하일 때까지 반복한다. 즉, 제곱수 pow의 배수를 순차적으로 마킹한다.
2. check[(int) ((j * pow) - min)] = true;는 check 배열에서 j * pow 값이 범위 내에 있을 때, 해당 인덱스를 true로 설정한다.
   예를 들어, min = 10, pow = 4, j = 3일 때 j * pow = 12가 된다. check[(12 - 10)] = true; 즉, check[2]를 true로 설정하여 12는 제곱수의 배수임을 표시한다.

5️⃣ 배수 마킹 후, 제곱ㄴㄴ수 개수 세기

1. count는 제곱ㄴㄴ수의 개수를 세는 변수입니다. check 배열에서 false인 값을 세면 된다.
   check[i]가 true이면 i + min이 제곱수의 배수로 제외된 값이기 때문
2. for (int i = 0; i <= max - min; i++)는 check 배열을 순차적으로 돌며 false인 값(즉, 제곱수의 배수가 아닌 값)을 찾는다.
3. if (!check[i]) { count++; }는 check[i]가 false일 때, 즉 제곱수의 배수가 아니면 count를 증가시킨다.

 

 

😊 느낀 점

꽤나 어려운 문제였다.. 단순히 소수 찾던 것처럼 배수 대신 제곱수를 제거해서 찾으면 되는 줄 알았는데,, 쉽지 않았다.. 특히 범위를 어떻게 나눠서 처리해야 할지 고민이 많이 되었다. min의 최댓값이 1,000,000,000,000으로 매우 클 것 같았지만, 실제로는 min과 max 사이의 수들만 다루면 되므로, 1,000,000개의 데이터만 확인하면 된다는 사실을 깨달았다! 배수 처리에서 중요한 점은 start_index를 정확히 계산하여 배수들의 첫 번째 위치를 맞추는 것이었다. 이 부분이 잘못되면 잘못된 값들이 마킹되기 때문에, 계산 과정에서 범위를 정확히 맞추는 것이 매우 중요하다는 것을 또 한 번 느꼈다.