백준 10434번 : 행복한 소수

문제

10434번: 행복한 소수 (acmicpc.net)

10434번: 행복한 소수

정수가 입력될 때 그 정수가 행복한 소수인지를 출력하는 문제.
행복한 소수란, 각 자리의 제곱의 합을 구하는 것을 반복했을 때 1이 나오는 소수

---

아이디어

❗어떤 소수가 행복한 소수가 아닌 경우, 각 자리 제곱의 합은 어떤 패턴을 띄게 되어있다.

• 행복한 소수는 우선 소수여야 한다. -> 1과 소수가 아닌 수는 바로 NO 출력
• 입력된 수가 소수이면, 제곱의 합을 구한 다음 이미 나온 수인지를 반복문 안에서 확인한다.
• 이미 나온 수인지 확인하는 방법 : 합이 나오면, contains 함수로 포함 여부를 확인하고 아니라면 list에 저장
• 결과가 이미 나온 수이거나, 1이면 반복문을 탈출한다.
• 결과가 1이면 YES를 아니면 NO를 출력한다.

package happyNum;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // times 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int times = Integer.parseInt(br.readLine());

        for(int i=0; i<times; i++){
        	// 인덱스와 정수 입력받기
            StringTokenizer st = new StringTokenizer(br.readLine());
            String idx = st.nextToken();
            String originNum = st.nextToken();
            int origin = Integer.parseInt(originNum);
            
            char[] num = originNum.toCharArray(); // 각 자리수마다 끊어 저장하는 배열
            ArrayList<Integer> list = new ArrayList<>(); // 제곱합을 저장할 리스트
            int result; // 제곱 합이 담길 변수
            
            // 1이거나 소수가 아니면 NO 출력
            if(origin==1 || !isPrim(Integer.parseInt(originNum))){
                System.out.println(idx+" "+originNum+" "+"NO");
                continue;
            }

            while(true){
                // 각 자리의 제곱의 합을 구하는 부분
                result = 0;
                for (int j = 0; j < num.length; j++) {
                    result += (num[j] - 48) * (num[j] - 48);
                }
                
                // 이미 나온 숫자이거나 1이면 break
                if(list.contains(result) || result==1){
                    break;
                }
                
                // 새로운 숫자이면 list에 더하고 num 초기화
                list.add(result);
                num = String.valueOf(result).toCharArray();
            }
            System.out.println(idx+" "+originNum+" "+((result==1)?"YES":"NO"));
        }
    }
    
    // 소수 판별 함수
    public static boolean isPrim(int n) {
        boolean b = true;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if(n%i==0){
                b=false;
            }
        }
        return b;
    }
}

---

배운 내용

1. 소수인지 판별하는 함수
1부터 자기 자신까지 mod 연산의 결과가 0을 만족하는 수가 1과 자시 자신이여야만 한다.
이를 응용하면 '2부터 자기 자신의 제곱근까지 % 결과가 0이 되면 소수가 아님'을 알 수 있다.
(어떤 수 N이 A*B 의 결과라면, A와 B중 하나는 무조건 N의 제곱근 보다 작으므로)
이때, for문에서 (int i=2; i<=Math.sqrt(n); i++)로 제곱근까지는 포함을 해줘야 한다는 것을 주의하자.

2. br.readLine과 st.nextToken
br.readLine은 줄 단위로 입력받는 함수이고, 하나의 줄로 입력된 스트링을 반환한다.
st는 StringTokenizer의 객체이고, StringTokenizer 생성자의 인자로 String을 넣어 생성한다.
st.nextToken은 인자루 준 String을 띄어쓰기 단위로 이동하며 받아오는 함수이다.

사용 예시 :

StringTokenizer st = new StringTokenizer(br.readLine());
String s = st.nextToken();

 

3.구현 문제를 푸는 자세 
이 문제는 '어떤 소수가 행복한 소수가 아닌 경우, 각 자리 제곱의 합은 어떤 패턴을 띈다'는 규칙을 눈치채야 풀 수 있는 문제였다. '만약 비슷한 문제가 주어졌을 때 내가 규칙을 파악하면 못 어떡하지?' 라는 생각을 많이 하게 되었다. 그런 상황을 대비해서 구현문제인데, 어떻게 해결해야할지 모르겠으면, 하나씩 써보면서 규칙을 찾는 것을 습관화 해야겠다! 

4. HashSet.add( )
자료구조에 저장이 되었는지를 검사하는 방법으로 나는 contains를 사용했는데,
HaseSet.add(obj)의 방법도 있다는 것을 알게 되었다.
HaseSet.add(obj)은 인자의 obj가 이미 존재하는 값이면 -1을, 중복되지 않은 값이면 1을 리턴하고 obj를 추가하므로
contains로 검사를 하고, true인 경우 add하는 방법보다 더 간결하게 짤 수 있다는 장점이 있다.

5. 정수의 각 자리수에 접근하는 방법
while(n>0){ int remain = n%10; n/=10; }의 방법으로도 정수의 각 자리수에 접근할 수 있다.