[백준] 9421번. 소수 상근수(JAVA)

문제

https://www.acmicpc.net/problem/9421

---

풀이(20분)

import java.io.*;
import java.util.*;

public class Main {

	static int n;
	static Set<Integer> yes = new TreeSet<>(); // 이전에 되는 것으로 확인이 되었던 값들
	static Set<Integer> no = new HashSet<>(); // 이전에 안 되는 것으로 확인이 되었던 값들
	static List<Integer> primes = new ArrayList<>(); // 소수 리스트
	static Set<Integer> visited = new HashSet<>(); // 반복이 되는 것을 체크

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());

		isPrime();
		for (int i : primes) {
			visited.clear(); // 반복 집합 초기화
			visited.add(i);
			if (dfs(i)) {
				yes.add(i);
			}
		}

		StringBuilder sb = new StringBuilder();
		for (int i : yes) {
			if (i > n) {
				break;
			}
			if (primes.contains(i)) {
				sb.append(i).append("\n");
			}
		}

		System.out.println(sb);
	}

	static boolean dfs(int num) { // 반복 탐색
		int square = squareNum(num); // 제곱수
		if (visited.contains(square)) { // 반복되는 것을 확인하고 있다면
			return false; // 실패
		} else {
			visited.add(square);
		}
		if (square == 1) { // 1이라면 성공
			yes.add(num);
			return true;
		}
		if (yes.contains(square)) { // 되었다면 체크
			return true;
		}
		if (no.contains(square)) { // 불가능하다면 체크
			return false;
		}

		boolean flag = dfs(square);
		if (flag) {
			yes.add(num);
		} else {
			no.add(num);
		}

		return flag;
	}

	// 에라토스테네스의 체
	static void isPrime() {
		boolean[] isPrime = new boolean[n + 1];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;

		for (int i = 2; i <= Math.sqrt(n); i++) {
			if (!isPrime[i]) {
				continue;
			}
			for (int j = i * i; j <= n; j += i) {
				isPrime[j] = false;
			}
		}

		for (int i = 2; i <= n; i++) {
			if (isPrime[i]) {
				primes.add(i);
			}
		}
	}

	// 제곱 수 확인
	static int squareNum(int num) {
		int squareNum = 0;
		while (num / 10 > 0) {
			squareNum += (num % 10) * (num % 10);
			num /= 10;
		}

		squareNum += num * num;
		return squareNum;
	}
}

---

문제 풀이 전략

 

전체 흐름 요약

1. 입력값 n을 받음
   → 1 ~ n 범위 안의 수 중에서 확인을 진행합니다.
2. 에라토스테네스의 체로 소수 목록 생성
   → primes 리스트에 모든 소수를 저장합니다.
3. 각 소수에 대해 ‘상근수(Happy Number)’ 판별 수행
   • 상근수: 각 자리의 제곱을 반복해서 더했을 때 결국 1이 되는 수
   • 예: 7 → 49 → 97 → 130 → 10 → 1 ✅

상근수 판별 로직 (dfs)

• visited: 이미 계산한 숫자를 저장해 순환(무한 반복) 방지
• yes: 이미 상근수로 판정된 숫자
• no: 상근수가 아닌 것으로 판정된 숫자

1. 현재 수의 각 자리 제곱의 합을 계산 (squareNum)
2. 이미 방문한 적 있는 수라면 → 순환 발생 → 실패 (false)
3. 결과가 1이라면 → 상근수 성공 (true)
4. 이미 성공(yes)이나 실패(no)로 판정된 값이면 그대로 결과 반환
5. 그 외의 경우 → 재귀 호출로 계속 탐색

• 탐색 결과에 따라 현재 숫자를 yes 또는 no 집합에 저장합니다.

출력

모든 소수 중에서 n 이하인 수 중 yes 집합(상근수)에 포함된 값만 출력합니다.