[알고리즘]뒤집은 소수

설명

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

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

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

 

입력

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

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

출력

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

예시 입력

9
32 55 62 20 250 370 200 30 100

예시 출력

23 2 73 2 3

 

문제 풀이

 입력 받은 숫자를 뒤집는 것이 해당 문제의 핵심이다. 뒤집는 방법의 여러 방법이 있겠으나, 입력받은 수를 10으로 나눈 나머지를 10씩 곱하여 뒤집는 방법으로 해결했다. StringBuilder 클래스의 reverse도 방법이 되겠으나, 형변환을 해야하니 비효율적일 것이라 판단했다.

 

public List<Integer> solution(int n, int[] arr) {
    for (int i = 0; i < n; i++) {
        int tmp = arr[i];
        int value = 0;

        while (tmp > 0) {
            value *= 10;
            value += tmp%10;
            tmp = tmp/10;
        }
        arr[i] = value;
    }

- arr[i]의 값을 변수  tmp에 대입한다.

- value는  tmp의 값이 0보다 클 때 까지 10씩 곱한다.

- value에 tmp를 10으로 나눈 나머지를 더해준다.

- 위 과정을 모두 수행하면 tmp를 10으로 나눠주고, 0보다 클때까지 해당 과정을 반복한다.

 

숫자 1230을 해당풀이 방법으로 뒤집어보면,

1. value는 0이므로 0*10 = 0. // value = 0

2. 1230/10의 나머지는 0이므로 0+0 =0. // value = 0

3. tmp를 10으로 나누면 1230 / 10 = 123. // tmp = 123

---- while문 반복----

4. value는 0이므로 0*10 = 0. // value = 0

5. 123/10의 나머지는 3이므로 0+3 = 3. // value = 3

6. tmp를 10으로 나누면 123/10 = 12. // tmp = 12

---- while문 반복----

7. value는 3이므로 3*10 = 30. // value = 30

8. 12/10의 나머지는 2이므로 30+2 = 32. // value = 32

9. tmp를 10으로 나누면 12/10 = 1. // tmp = 1

---- while문 반복----

10 value는 32이므로 32*10 = 320. // value = 320

11. 1/10의 나머지는 1이므로 320+1 = 321. // value = 321

12. tmp를 10으로 나누면 1/10 = 0. // tmp = 0

13. tmp는 0이므로 반복문을 종료하고, value의 최종값은 321이다.

 

1230의 뒤집은 수는 321이니 정확하게 수행했다.

 

소수를 찾는 방법은 많은 방법이 있으니 설명을 생략한다.

 

전체소스

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main m = new Main();

        int n = kb.nextInt();
        int[] arr = new int [n];

        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        List<Integer> answer = m.solution(n, arr);

        for (int i = 0; i < answer.size(); i++) {
            System.out.print(answer.get(i) + " ");
        }
    }

    public List<Integer> solution(int n, int[] arr) {
        List<Integer> answer = new ArrayList<>();
        
		// 숫자 뒤집기
        for (int i = 0; i < n; i++) {
            int tmp = arr[i];
            int value = 0;

            while (tmp > 0) {
                value *= 10;
                value += tmp%10;
                tmp = tmp/10;
            }
            arr[i] = value;
        }
	
    	// 소수 찾기
        for (int i = 0; i < n; i++) {
            int j;
            for (j = 2; j <= arr[i]; j++) {
                if (arr[i] % j == 0) {
                    break;
                }
            }
            if (j == arr[i]) {
                answer.add(arr[i]);
            }
        }

        return answer;
    }

}