[JAVA11/알고리즘]2-6 뒤집은 소수

문제

N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하는 프로그램을 작성하세요.

 

예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력한다. 단 910를 뒤집으면 19로 숫자화 해야 한다.

첫 자리부터의 연속된 0은 무시한다.

입력

첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다.

 

각 자연수의 크기는 100,000를 넘지 않는다.

 

출력 

첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.

예시 입력 1 

9
32 55 62 20 250 370 200 30 100

예시 출력 1

예시 출력 1

 

23 2 73 2 3

 

CODE
 

import java.util.*;

public class Main {
    public static boolean isPrime(int num){
        if(num == 1) return false;
        for(int i=2; i<=Math.floor(Math.sqrt(num)); i++){
            if(num%i==0) return false;
        }
        return true;
    }
   public static ArrayList<Integer> solution(int n,int[] arr){
       ArrayList<Integer> answer = new ArrayList<>();
        for(int i=0; i<n; i++){
            int tmp = arr[i];
            int res = 0;
            while(tmp>0){
                int t= tmp%10;
                res =res*10+t;
                tmp = tmp/10;
            }
            if(isPrime(res)) answer.add(res);
        }

       return answer;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int [] arr = new int[n];
        for(int i=0;i<n; i++){
            arr[i]= in.nextInt();
        }

        for(int x : solution(n,arr)){
            System.out.print(x + " ");
        }
    }
}

해결 

입력된 자연수를 뒤집은 뒤 그 뒤집은 수가 소수인지 판별하는 문제이다.

먼저 함수 2개를 만들었다.

 

입력받은 수가 소수인지를 판별하는 함수 boolean isPrime(int num)

그리고 소수들을 담은 배열을 리턴해주는 ArrayList<Integer> solution(int n, int[] arr)

 

먼저, isPrime에 대해서 알아보자.

소수이면 true, 소수가 아니면 false를 리턴해준다.

입력받은 num을 num의 제곱근까지만 나눠주고 그중 나눠지는 것이 있으면 false를 리턴해준다.

여기서 제일중요한건,Math.floor(Math.sqrt(num))을 이용해서 제곱근까지 for문을 돌린것이다.

뭐 그냥 num까지 해도 상관은 없지만 조금 더 효율적인 프로그램을 위해서 제곱근까지 하였다.

 

Math.floor 은 내림을, Math.sqrt는 제곱근을 의미한다. 제곱근은 double의 자료형을 반환하기 때문에  내림을 이용하여 정수로 만들었다.

 

제곱근보다 작은 정수 중 제일 큰 정수까지 비교 작업을 해도 상관이 없다. 그 수보다 큰 정수들로 나눠봤자 어짜피 나눠떨어지지 않기 때문이다.

 

다음,solution 에 대해서 알아보자.

 for(int i=0; i<n; i++){
            int tmp = arr[i];
            int res = 0;
            while(tmp>0){
                int t= tmp%10;
                res =res*10+t;
                tmp = tmp/10;
            }

이 함수의 for문을 가져와봤다.

정수를 뒤집는 과정인데, tmp 에 정수를 담고 이것을 10으로 나눈 나머지는 맨 끝자리를 의미한다.

그것을 res에 더해준다.

tmp = tmp/10을 해주면 맨끝자리가 탈락된 정수가 다시 남는다.

이것을 똑같은 과정을 또 반복해준다. 그리고 중요한것은 맨 끝자리를 res에 더해줄때 원래 있던 res에 10을 곱해줘야한다.

이렇게 되면 원래 res에 있던 수의 자리가 앞으로 한칸씩 땡겨지는 것과 똑같다.

결과