[백준] 10434번. 행복한 소수(JAVA)

문제

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

---

풀이(8분)

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

class Main{

    static final String no = " NO";
    static final String yes = " YES";

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int P = Integer.parseInt(br.readLine()); // 테스트 케이스

        StringBuilder sb = new StringBuilder();
        while(P-- > 0){
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int num = Integer.parseInt(st.nextToken());
            sb.append(t).append(" ").append(num);
            if(isPrime(num) && isHappy(num)){
                sb.append(yes);
            }else{
                sb.append(no);
            }
            sb.append("\n");
        }

        System.out.println(sb);

    }

    static boolean isPrime(int num){ // 소수인지 판별하는 메서드
        if(num == 1){
            return false;
        }
        for(int i = 2; i <= Math.sqrt(num); i++){ // 루트범위까지만 탐색
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }

    static boolean isHappy(int num){ // 행복한 수인지 판별
        Set<Integer> set = new HashSet<>();
        while(num != 1 && !set.contains(num)){
            set.add(num);
            num = sumOfSquares(num);
        }

        return num == 1;
    }

    static int sumOfSquares(int num) { // 제곱의 합을 구하는 메서드
        int sum = 0;
        while (num > 0) {
            int digit = num % 10;
            sum += digit * digit;
            num /= 10;
        }
        return sum;
    }
}

---

문제 풀이 전략

 

소수인지와 행복한 수인지를 각각 구분했다.

소수인지, 행복한 수인지 어떤 것을 우선 비교하는 것이 나은지를 생각해 보았지만 쉽게 결론이 나지 않아 각각 비교해 보았다.

 

아래가 isPrime()가 우선된 것이고, 위가 isHappy()가 우선된 것이다.

큰 차이는 없었지만 일반적으로 Math.sqrt()를 통해 문제 조건의 범위인 10000에 대해 더욱 적합한 연산이 이루어지나 보다.