Cos Pro 1급 - 샘플 문제 풀이 4차 10번 (소수의 제곱수의 개수 구하기)

문제 지문 #10

자연수를 제곱한 수는 제곱수, 세제곱한 수는 세제곱수라고 합니다. 예를 들어 2^2 = 4는 제곱수, 3^3 = 27은 세제곱수입니다.

두 자연수 a, b가 주어질 때 a 이상 b 이하인 자연수 중 _소수_의 제곱수와 세제곱수의 개수를 구하려 합니다. 예를 들어 a = 6, b = 30일 때 소수의 제곱수는 [9, 25]로 2개, 소수의 세제곱수는 [8, 27]로 2개로 총 4개입니다.

두 자연수 a, b가 매개변수로 주어질 때, a 이상 b 이하인 제곱수와 세제곱수의 개수의 합을 return 하도록 solution 메서드를 완성해주세요.

---

#####매개변수 설명

두 자연수 a, b가 solution 메서드의 매개변수로 주어집니다.

• a, b는 각각 1 이상 1,000,000,000 이하인 자연수입니다.
• a ≤ b인 경우만 입력으로 주어집니다.

---

#####return 값 설명

a 이상 b 이하인 제곱수와 세제곱수의 개수의 합을 return 해주세요.

---

#####예시

a	b	return
6	30	4

#####예시 설명

6 이상 30 이하인 수중 소수의 제곱수는 다음과 같습니다.

• 3^2 = 9
• 5^2 = 25

소수의 세제곱 수는 다음과 같습니다.

• 2^3 = 8
• 3^3 = 27

따라서 4를 return 하면 됩니다.

728x90

 

혼자 풀이

전체 코드를 완성하는 문제입니다. 난이도는 쉬운 편입니다. 
10억 이하 자연수인 a, b 사이에 소수의 제곱수와 세제곱수가 몇 개인지 찾는 문제입니다.

세제곱을 한 값이 10억(1000,000,000) 이하여야 되므로 소수는 1000보다 작아야 합니다.
즉, 소수는 1000 이하를 찾으면 됩니다. 

소수를 찾아서 주어진 a이상 b이하인지 검사하고 조건을 만족하면 반환 값을 증가시켰습니다.

// 다음과 같이 import를 사용할 수 있습니다.
import java.util.*;

class Main {
    public int solution(int a, int b) {
        // 여기에 코드를 작성해주세요.
        int answer = 0;
			
        //a와 b가 10억 이하 자연수이므로 1천 이하의 소수의 제곱수와 세제곱수만 가능			
        // 1천 이하의 소수를 구하고, 소수의 제곱수와 세제곱수가 a,b 사이에 들어가는 개수를 구함			
        //1천 이하의 소수를 구하기
        ArrayList<Integer> sosu = new ArrayList<>();

        boolean isSosu;
        //2부터 1000까지의 수가 소수인지 검사
        for(int i=2;i<1000;i++){
            isSosu=true;
            //i가 j로 나누어 떨어지면 소수가 아님(i가 2일때는 for문 실행되지 않음)
            for(int j=2;j<i;j++){
                if(i%j==0){
                    isSosu=false;
                    break;
                } 
            }
            //for문 수행결과 isSosu가 true이면 sosu ArrayList에 추가
            if(isSosu){
                sosu.add(i);						
            }					
        }
        //소수의 제곱수와 세제곱수의 개수 구하기			
        for(int i =0;i<sosu.size();i++){					
            //소수의 제곱수가 a이상 b이하이면 answer를 1증가
            if((Math.pow(sosu.get(i),2)>=a) && (Math.pow(sosu.get(i),2)<=b)){												
                answer++;
            } 
            //소수의 세제곱수가 a이상 b이하이면 answer를 1증가
            if((Math.pow(sosu.get(i),3)>=a) && (Math.pow(sosu.get(i),3)<=b)){												
                answer++;
            }  					
        }
      	return answer;
    }

 

정답

공식 홈페이지에서 제공하는 정답은 없습니다. 별도 샘플 문제 강의 자료에서 가져왔습니다.
제가 앞서 했던 방식은 bruteforce 방식으로 모든 case에 대해 대입해서 답을 찾는 방식인데,
아래 정답 코드는 에라토스테네스의 체를 이용한 방식입니다.
에라토스테네스의 체 방식은 체로 입자가 큰 알갱이를 거르는 것처럼 특정 자연수 이하의 소수만을 골라내는 방법입니다.

소수 여부를 검사해야 되는 범위를 n이라고 하면 n 이하의 각 수의 배수를 순차적으로 지워가는 방식입니다.
뒤로 갈수록 검사해야 되는 범위가 줄어들게 되며, 검사 중인 수 n의 최대 약수는 루트 n이므로 검사대상이 루트 n보다 크게 되면 검사를 중단합니다..

class T_Solution10_2 {
    public int solution(int a, int b) {
        int answer = 0;
	  	int k=(int)(Math.sqrt(b));        //마지막 소수는 b의 제곱근
	    boolean arr[] = new boolean[k+1];
	    
        //k개의 요소를 True로 초기값 설정
        for(int i=2; i<=k; i++) 
      	   arr[i]=true;           
       
        
        //소수의 배수에 해당하는 값들을 false로 지우기
        for(int n=2 ; n<=Math.sqrt(k) ; n++) {
        	if(arr[n]==true) {                //n이 소수이면      		
    		  for(int j=(n+n);j<=k;j=(j+n)) { //소수 n의 배수들을 false로 변경
    		      arr[j]=false;
    		  }
	        }
         }
              
        for(int n=2 ; n<arr.length ; n++) {
         	if (arr[n]==true) {    
         		if(n<=k) {
	         		int tmp=n*n;
	        		if (a<= tmp && tmp<=b)  { 
	        			answer+=1;
	        			System.out.println(answer+" " +n+"의 제곱:"+tmp);
	        		}        		
         		}
        		if(n<=1000) {
	        		int tmp2=n*n*n;
	        		if (a<= tmp2 && tmp2<=b) {
	        			answer+=1;
	        			System.out.println(answer+" "+n+"의 세제곱: "+tmp2);
	        		}
	        	}
        	}
        }
        return answer;
    }
}

 

실습은 아래 참고

2022.10.25 - [Programming/Cos Pro 1급] - Cos Pro 1급 공부 사이트 추천 - 구름 에듀(https://edu.goorm.io/)

Cos Pro 1급 공부 사이트 추천 - 구름에듀(https://edu.goorm.io/)