[JAVA] 백준 1557번 제곱ㄴㄴ

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

1557번: 제곱 ㄴㄴ

이전 백준 문제는 화면을 캡쳐하고 몇번째 줄은 어떤 의미인지 설명했는데,

이 문제는 다시 풀 때 캡쳐해서 줄별로 설명하지 않고 의식의 흐름대로 주석으로 정리하면서 풀어보았다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int max = 100000;
    static List<Integer> list = new ArrayList<>();

    static int getSqureCnt(int index, long num, long tempAns){
        if(index>=list.size()){
            return 0;
        }
        if(num*list.get(index) > tempAns){
            return 0;
        }
        int ans = 0;
        ans += tempAns/(num*list.get(index));
        ans += getSqureCnt(index+1, num, tempAns);
        ans -= getSqureCnt(index+1, num*list.get(index), tempAns);
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();   //정수 K번째에 있는 제곱배수가 아닌 수 구하기
        // K = 10 -> 1,2,3,5,6,7,10,11,13,14
        // n = 14 라하면, 14 안에는 제곱배수가 4,8,12, 9 이므로 14-4 = 10
        // k가 10일때 정답은 14.
        // 14를 먼저 구하고 14 안에 있는 제곱수의 배수의 개수를 빼준 것이 답이다.

        //제곱수를 먼저 구한다.
        //제곱수는 4, 9, 16, 25... 16은 4의 제곱수의 배수이므로 제외해야한다.
        //소수의 제곱수를 구해야 중복되는 값이 제외된다.
        //소수가 아닌 수(1이 아닌 다른 수로 나누어지는 수)의 제곱은
        //-이미 이전에 구한 제곱수의 배수가 되므로 제외할 수 있다.
        //예를들어, 4,6,8은 2의 배수이므로 4,6,8의 제곱수는 2의 제곱수의 배수가 되므로 제외한다.
        boolean[] d = new boolean[max+1];
        for(int i=2; i<=max; i++){
            int square = i*i;
            if(d[i]) continue;
            for(int j=i; j<=max; j+=i){
                d[j] = true;
            }
            list.add(square);
        }

        //k번째 제곱ㄴㄴ수를 구하기 위해서는 ans값을 먼저 알아야한다.
        //ans를 알아야 그 안에 제곱수의 배수의 수를 구하고 ans가 몇번째 위치한 수(k)인지 알수있다.
        //이분탐색을 이용한다.
        long left = 0;
        long right = Integer.MAX_VALUE;
        long ans = 0;
        while(left < right){
            long mid = (left + right) / 2;
            int tempAns = (int)mid - getSqureCnt(0, 1, mid);
            if(tempAns < k){
                left = mid + 1;
            }else{
                ans = mid;
                right = mid;
            }
        }
        System.out.println(ans);
        sc.close();
    }

}

이분탐색을 이용하는 while(left<right)부분은 left만 mid+1 인 부분이 이분탐색을 처음 접했던 때는 참 헷갈렸었다.

3을 2로 나눠도 mid=1이고 2를 2로 나눠도 mid=1이 나오니, left값은 mid+1을 해줬고

while(left<=right)를 한다면 left=mid+1, right=mid-1 해주면 된다.