인프런 커뮤니티 질문&답변

저자 선생님 안녕하세요

좋은 교재와 강의 잘 보고 있습니다.

강의가 없는 1016번 문제에 대해 오래동안 고민을 해도 해결이 안되어 질문을 드리고 싶은데, 받아주시면 정말 감사하겠습니다.

시간초과가 난 전체 코드입니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader is = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(is);
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        long min = Long.parseLong(st.nextToken());
        long max = Long.parseLong(st.nextToken());
        // 최댓값과 최솟값의 차이만큼 배열 선언하기
        boolean[] Check = new boolean[(int)(max-min+1)];
        // 2의 제곱수인 4부터 Max보다 작거나 같은 값까지 반복하기

    /*  저자님 코드(정답) 
     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++){//제곱수를 true로 변경하기
                Check[(int)((j*pow)-min)] = true;
            }
        }
        */
        
        //제 코드(시간초과)
       for(long i=2; i*i<=max; i++){
            long pow = i*i;//제곱수
            for(long j=1; (j*pow)<=max; j++){
                long t= j*pow;//제곱수의 배수
                if((min<=t) && (t<=max)){//제곱수의 배수가 min과 max 범위 안이면
                    Check[(int)(t-min)] = true; //제곱수의 배수 표시
                }
            }
        }
       //

        long count = 0;
        for(long i = 0; i<=max-min; i++){
            if(!Check[(int)i]){
                count++;
            }
        }
        System.out.println(count);
    }
}

위의 전체 코드에서 저자 선생님 코드를 주석 /* */ 로 감싸고

제 코드를 바로 아래에 작성했는데, 보시기 힘들 것 같아서 보라색과 초록색으로 구분한 스크린샷을 같이 올려드립니다.

제 코드의 경우, 백준 문제에서 보여준 테스트케이스는 통과하는데

시간초과가 발생했습니다.

그래서 많은 테스트케이스를 시도해봤는데

입력

1000000000000 1000001000000

이 테스트케이스에서

저자 선생님 코드는 제대로 작동을 하고, 제 코드는 시간초과가 발생하는 것 같았습니다.

하루종일 고민해도 그 이유가 도저히 이해가 안돼서, 질문을 드리고 싶습니다.

가르쳐주시면 정말 감사하겠습니다.

읽어주셔서 감사합니다.

+오후 8시에 질문을 추가드립니다.
시간초과가 안나는 핵심 로직이

long start_index = min/pow;//최솟값/제곱수
if(min%pow!=0){
     start_index++;
         }

같은데 이 부분이 이해가 너무 어렵습니다..
이 코드를 더 자세하게 가르쳐주시면 감사하겠습니다.