섹션 2. Array - 6. 뒤집은 소수

📌 문제 설명

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

• 예를 들어 32를 뒤집으면 23이고, 23은 소수이므로 23을 출력합니다.
• 숫자를 뒤집었을 때 앞자리에 오는 연속된 0은 무시합니다.

---

📝 입력 & 출력

입력

• 첫 줄에 자연수의 개수 N(3 ≤ N ≤ 100)이 주어지고, 다음 줄에 N개의 자연수가 주어집니다.
• 각 자연수는 100,000을 넘지 않습니다.

출력

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

---

🔸 예제 입력 & 출력

예제 입력 1

9
32 55 62 20 250 370 200 30 100

 

예제 출력 1

23 2 73 2 3

---

💡 해결 방법

1. 입력받은 각 자연수를 뒤집습니다.
2. 뒤집힌 수가 소수인지 판별합니다.
3. 소수인 경우 결과 리스트에 추가하여 출력합니다.

---

💻 코드 구현 (Java)

package partArray;

import java.util.*;

public class Problem6 {
	public boolean isPrime(int num) {
		if(num == 1) return false;
		for(int i = 2; i < num; i++) {
			if(num % i == 0) return false;
		}
		return true;
	}
	
	public ArrayList<Integer> solution(int num, int[] arr) {
		ArrayList<Integer> result = new ArrayList<>();
		for(int x : arr) {
			int res = 0;
			while(x > 0) {
				res = res * 10 + x % 10;
				x = x / 10;
			}
			if(isPrime(res)) result.add(res);
		}
		return result;
	}
	
	public static void main(String[] args) {
		Problem6 T = new Problem6();
		Scanner kb = new Scanner(System.in);
		int num = kb.nextInt();
		int[] arr = new int[num];
		for(int i = 0; i < num; i++) {
			arr[i] = kb.nextInt();
		}
		for(int x : T.solution(num, arr)) {
			System.out.print(x + " ");
		}
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 소수 판별 메서드

public boolean isPrime(int num) {
	if(num == 1) return false;
	for(int i = 2; i < num; i++) {
		if(num % i == 0) return false;
	}
	return true;
}

• 1은 소수가 아니므로 제외합니다.
• 2부터 자기 자신 직전까지 나누어 떨어지는지 확인하여 소수를 판별합니다.

2️⃣ 숫자 뒤집기

int res = 0;
while(x > 0) {
	res = res * 10 + x % 10;
	x = x / 10;
}

• 숫자를 거꾸로 뒤집습니다.

3️⃣ 뒤집힌 수가 소수일 때 결과 추가

if(isPrime(res)) result.add(res);

• 뒤집힌 수가 소수일 때 결과 리스트에 추가합니다.

---

⏳ 시간 복잡도 분석

• 숫자 뒤집기: 각 숫자의 자릿수만큼 반복 O(logN)
  • 이유: 숫자가 10으로 계속 나누어져 빠르게 줄어들기 때문입니다. 즉, 10^자릿수로 표현된 숫자는 10으로 몇 번 나누는지(로그 값)로 표현됩니다.

• 소수 판별: 현재 방식에서는 각 수를 2부터 자신보다 작은 수까지 전부 나눠봅니다. 최악의 경우 O(M)의 시간복잡도를 가지며, 이 작업을 N번 수행하면 O(N × M)의 시간이 듭니다.
• 전체 시간 복잡도: 결국 숫자 뒤집기O(log M)보다 소수 판별 O(N × M) 이 더 크므로, 전체 복잡도는 O(N × M)가 됩니다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런