2023. 5. 2. 23:12ㆍ💻코딩/💡Baekjoon
[문제 링크]
1016번: 제곱 ㄴㄴ 수
어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수
www.acmicpc.net
import java.util.*;
public class Main {
static int count = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long min = sc.nextLong();
long max = sc.nextLong();
boolean[] check = new boolean[1000001];
long end = (long)Math.sqrt(max);
//에라토스테네스의 체 원리
for(long i = 2; i < end+1; i++) {
long temp = i*i;
long start = 0;
if(min % temp == 0) {
start = min / temp;
}else {
start = (min / temp) + 1;
}
for(long j = start; j*temp < max+1; j++) {
check[(int)((j*temp)-min)] = true;
}
}
for(int i = 0; i < (max-min+1); i++) {
if(check[i]==false) {
count++;
}
}
System.out.println(count);
}
}
이번 문제는 겉보기에 쉬워보였고, for문과 if문을 통해 쉽게 구현했지만 문제가 있었다.
바로 시간초과이다..❕이는 for문을 여러번 돌고 min, max의 숫자 자체가 커서 생기는 오류였다.
이를 해결하기 위해서는 '에라토스테네스의 체 원리' 를 사용해야 한다.
에라토스테네스의 체 원리란, 소수를 빠르게 찾는 방법이다.
2부터 시작하게 될 경우, 차례대로 소수의 배수를 제거한다. (이때, 본인은 제거하지 않는다.)
이를 반복하면 최종적으로 모든 소수가 남는다.
에라토스테네스 체 원리에 대한 쉬운 이해와 설명은 아래의 블로그를 참고하길 바란다.
[JAVA] 소수 찾기 - 에라토스테네스의 체
문제에 대해서는 여기를 클릭하여 가면 된다. 이번에 프로그래머스를 풀면서 에라토스테네스의 체를 사용하여 이 알고리즘을 설명하는 김에 문제풀이도 같이하려 가지고 왔다. 일단 에라토스
krapoi.tistory.com
이 문제에서는 boolean 타입의 check 배열을 만들어 소수를 체크할 수 있도록 하였고,
입력값을 min = 1, max = 10으로 주었을 때, 가장 작은 제곱수인 4를 시작으로
min을 4로 나누었을 때, 나누어 떨어지면 start의 값을 몫으로, 그렇지 않으면 몫 + 1값을 가져가도록 하고,
지금은 min의 값이 1이므로 start = 1이된다.
1*4 = 4이고, 4는 1~10 사이의 값이므로 check 배열의 해당 인덱스 값을 ture로 지정한다.
그 이후 제곱수의 수를 늘려가며 반복하고 최종적으로 check 배열의 값이 false인 제곱 ㄴㄴ수의 수를 출력하면 된다.
'💻코딩 > 💡Baekjoon' 카테고리의 다른 글
[백준] 1021 회전하는 큐 (2) | 2023.12.13 |
---|---|
[백준] 1015 수열 정렬 (0) | 2023.05.18 |
[백준] 1014 컨닝 (0) | 2023.02.04 |
[백준] 1013 Contact (1) | 2023.01.16 |
[백준] 1012 유기농 배추 (2) | 2023.01.13 |