[코딩테스트] 백준 1016 자바

백준 1016

백준 1016 문제

해당 문제는 min의 값이 1,000,000,000,000으로 매우 큰 것 같지만 실제로 min과 max 사이의 수들 안에서 구하는 것이므로 1,000,000의 데이터만 확인하면 된다.

제곱수 판별을 일반적인 반복문으로 구하면 시간 초과가 발생하므로 에라토스테네스의 체 알고리즘 방식을 제곱수 판별 로직에 적용해 문제를 해결할 수 있다.

데이터를 순차적으로 탐색하는 것이 아니라 에라토스테네스의 체 방식으로 제곱수의 배수 형태로 탐색해 시간 복잡도를 최소화하는 것이 이 문제 풀이의 핵심이다.

package numbertheory.primenumber;

import java.util.*;

public class Boj1016 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long min = sc.nextLong(); // 최솟값
        long max = sc.nextLong(); // 최댓값

        // 최댓값과 최솟값의 차이만큼 배열 선언
        boolean[] check = new boolean[(int) (max - min + 1)]; // min ~ max 사이에 제곱수 판별 배열
        int count = 0; // 제곱이 아닌 수 카운트

        // 2의 제곱수인 4부터 max보다 작거나 같은 값까지 반복
        for (long i = 2; i * i <= max; i++) { // 단순 탐색이 아닌 제곱수 형태로 증가
            long pow = i * i; // 제곱수
            long start = min / pow; // 시작 인덱스

            if (min % pow != 0) { // 나머지가 0이 아니면
                start++; // 시작 인덱스 1 증가, 나머지가 있으면 1을 더해야 min보다 큰 제곱수에서 시작됨
            }

            for (long j = start; pow * j <= max; j++) { // 제곱수의 배수 형태로 탐색
                // j * pow가 max보다 작을 때 최솟값, 최댓값 사이의 제곱수이므로 check 배열에 저장
                check[(int) ((j * pow) - min)] = true; // 제곱수를 true로 변경
            }
        }

        for (int i = 0; i <= max - min; i++) { // 0부터 (max - min)까지 탐색
            if (!check[i]) { // check 배열에 제곱이 아닌 수라면
                count++; // count 증가
            }
        }

        System.out.println(count); // count 출력
    }
}

풀이

1. 최솟값을 입력 받아 min에 저장한다.
2. 최댓값을 입력 받아 max에 저장한다.
3. 최댓값과 최솟값의 차이만큼의 크기를 가진 check 판별 배열을 선언한다.
4. 제곱이 아닌 수의 카운트 count를 0으로 초기화한다.
5. 2의 제곱수인 4부터 max보다 작거나 같은 값까지 반복한다.
   5-1. 제곱수 pow에 i * i를 저장한다.
   5-2. 시작 인덱스 start에 min / pow의 결과를 저장한다.
   5-3. min % pow가 0이 아니면 1를 더해야 min보다 큰 제곱수에서 시작되기 때문에 start를 1 증가시킨다.
   5-4. 제곱수의 배수 형태로 탐색한다.
   5-5. j * pow가 max보다 작을 때 최솟값과 최댓값 사이의 제곱수이므로 check 배열에 저장한다.
   5-6. 제곱수를 true로 변경
6. 0부터 max - min까지 탐색한다.
   6-1. check 배열에 제곱이 아닌 수라면 count를 증가시킨다.
7. count를 출력한다.