JAVA)백준 1016번 제곱 ㄴㄴ수

이 문제는 시간복잡도를 얼마나 효율적으로 풀수있는가를 보는 것이 관건이다.

직관적으로 풀면

import java.util.Scanner;

public class Main {
	public static void main(String[] arg) {
		long min, max;
		long k;
		int count=0;
		Scanner input = new Scanner(System.in);
		
		min = input.nextInt();
		max = input.nextInt();
		
		for(long i=min;i<=max;i++) {
			for(long j=1;j<max/3;j++)
				if(j*j == i) {
					count++;
				}	
			}
		k = (max-min)-count;
		System.out.println(k);
		}
	}

이렇게 풀순있다. 하지만 컴파일을 돌려보면 시간초과가 뜬다. 그이유는 수가 작으면 상관없지만 여기서 시간복잡도는 n^2이다. 따라서 max를 1,000,000,000,000까지 설정 할 수 있다. 따라서 시간이 기하급수적으로 증가하기떄문에 시간초과가 나온다. 여기서 에라토스테네스의 체라는 알고리즘을 사용해야한다. 일단 어떻게 사용했는지 코드를 살펴보자.

import java.util.Scanner;
import java.util.Arrays;
public class Main {
	static long min,max;
	public static void main(String[] arg) {
		Scanner input = new Scanner(System.in);
		
		min = input.nextLong();
		max = input.nextLong();
		choicenumber();
	}
	
	
	private static void choicenumber() {
		int end = (int)Math.sqrt(max);
		
		boolean []checkAarray = new boolean[1000001];
		Arrays.fill(checkAarray, false);
	
		for(long i =2; i<=end; i++) {
			long square = i*i;
			long start = ((min-1)/square+1)*square;
			for(long a = start; a<=max;a+=square) {
				checkAarray[(int) (a-min)]= true;
			}
		}
		int count =0;
		for(int i =0;i<(max-min+1);i++) {
			count+=(checkAarray[i]==true)?1:0;
		}
		System.out.print(max - min -count+1);
	}
	}

에라토스테네스의 체는 소수를 찾는 방법 중 하나이다. int를 사용하지 않고 long을 사용한이유는 int는 4bytes밖에 표현을 못하지만 long은 16bytes까지 표현할 수 있다. 따라서 여기서 max가 1,000,000,000,000까지 표현할수 있게 하려면 long 타입을 사용해야한다. 알고리즘을 설명해보자면, min과 max를 받아온뒤 choicnumber라는 함수를 하나 만들어 소수를 찾아 지워나가는 방식이다. 위에 알고리즘보다 효율성이 더 뛰어난다. 똑같이 만들어도 시간복잡도를 통해 더 효율적으로 문제를 풀 수 있다.