6. 뒤집은 소수

1. 문제

n개 입력

입력된 숫자들을 뒤집고 뒤집은 수가 소수이면 해당 수를 출력한다.

뒤집었을 때 첫 자리의 연속된 0은 무시한다. (ex 910 ㅡ> 019 ㅡ> 19) 

 

2 - 1. 나의 풀이

알바하면서 어떻게 풀어야할까 고민해봄.

1. 입력된 숫자를 뒤집기

2. 뒤집은 수 첫번째가 연속된 0일 경우를 해결

3. 소수인지 판단

위 과정을 거쳐서 출력하면 된다.

 

1. 입력된 숫자를 뒤집기

입력된 수를 String 타입으로 변환한다음 toCharArray()를 사용해 char[] tmp 에 저장한다.

그다음 tmp를 뒤집어 주는 알고리즘을 사용한다. (swap하면 된다.)

 

2. 뒤집은 수 첫번째가 연속된 0일 경우

이 경우 019 를 19로 바꿔줘야하는데 어떻게 하지 고민하다가, Integer.parseInt를 사용하면 0을 자동으로 제외해준다는 게 기억이 났다.

parseInt의 인자로 넣어주기 위해 tmp를 String으로 변환해준 다음, 해당 값을 인자로 넣어준다. Integer.parseInt(String..valueOf(tmp))

 

3. 소수 인지 판단

tmpInt는 뒤집은 수 이다.

이 수가 소수인지 판단후 출력만 하면 된다.

tmpInt가 2보다 작으면 무시하고(넘어가고)

tmpInt가 2이면 소수이므로 출력하고

tmpInt가 2보다 크면 소수인지 아닌지 판단하는 알고리즘을 사용한다.

 

여기서 난 두가지 개념을 사용했다.

첫 번째는 숫자의 제곱근을 활용해 소수 판단을 했다.

두 번째는 flag를 활용해서 모든 반복문을 거쳐서 나눠지지 않았을 경우 flag 를 true로 표시하고 반복문 마지막에 flag가 true인지 false인지 판단해서 해당 수를 출력할지 안할지 결정한다.

 

2 - 2. 나의 코드

package Algorythm_Array;

import java.util.Scanner;
import java.lang.Math;
public class Array06 {
    public static void solution(int[] intArr, int n) {
        for (int i = 0; i < n; i++) {
            char[] tmp = String.valueOf(intArr[i]).toCharArray();
            //System.out.println(tmp);
            for (int j = 0; j < tmp.length / 2; j++) {
                char tmp1 = tmp[j];
                tmp[j] = tmp[tmp.length - j - 1];
                tmp[tmp.length -j -1] = tmp1;
            }

            int tmpInt = Integer.parseInt(String.valueOf(tmp));
            boolean flag = true;
            if (tmpInt < 2) {
                continue;
            }else if(tmpInt ==2){
                System.out.print(tmpInt + " ");
            } else if (tmpInt > 2) {
                for(int j =2; j<= Math.sqrt(tmpInt);j++){
                    if(tmpInt % j == 0){
                        flag = false;
                        break;
                    }
                    flag = true;
                }
                if(flag == true)System.out.print(tmpInt + " ");
            }
        }


    }


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

        solution(intArr, n);


    }
}

 

 

3 - 1. 강의 풀이

1. 숫자 뒤집기

나의 풀이와 다르게 수학적 계산을 통해서 수를 뒤집었다. 이해 후 암기 하면 좋을 듯!

이렇게 하면 뒤집었을 때 앞이 0이 나오는 경우도 자연스럽게 해결된다!

int tmp = 뒤집을 수
int res = 0;
while(tmp > 0){
	int t = tmp % 10;
    res = res * 10 + t;
    tmp = tmp / 10; //tmp /=10;
}

2. 소수 판단

따로 메서드를 만듦

Math.sqrt(n)을 사용해도 제곱근 구하는 시간 때문인지 시간 차이가 별로 나지 않는다.

public static boolean isPrime(int n){
	if(n ==1)return false;
    else{
    	for(int i = 0 ; i < n ;i++){ //Math.sqrt(n)
        	if(n % i == 0) return false;
        }
        return true;
    }
}

 

3 - 2. 강의 코드

import java.util.ArrayList;
import java.util.Scanner;
import java.lang.Math;

public class String06_solution {
	//소수 판단 메서드
    public static boolean isPrime(int n) {
        if(n == 1) return false;
        else if (n >= 2) {
            for (int i = 2; i <n ; i++) { //i < Math.sqrt(n) 도 가능! 근데 시간 차이가 별로 없다?
                if (n % i == 0) return false;
            }
        }
        return true;
    }
    public static ArrayList<Integer> solution(int[] intArr, int n) {
        ArrayList<Integer> answer = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int tmp = intArr[i];
            int res=0;
            //숫자 뒤집는 알고리즘
            while(tmp > 0){
                int t = tmp % 10;
                res = res * 10 + t;
                tmp = tmp / 10; //tmp /=10;
            }
            //System.out.println(res); 테스트용
            if(isPrime(res)) answer.add(res);
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] intArr = new int[n];
        for (int i = 0; i < n; i++) {
            intArr[i] = sc.nextInt();
        }
        for (int x : solution(intArr, n)) {
            System.out.print(x + " ");
        }
    }
}

 

4. 얻어갈 점.

1. 숫자를 뒤집는 알고리즘 ㅡ> 매우 유용할 듯!!