[ 백준 ] 2312번 - 수 복원하기

< 문제 정보 >

[ 문제 ]

양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오

[ 예시 ]

• 입력 :
  2 // 테스트 케이스의 수
  6
  24
• 출력 :
  2 1
  3 1
  2 3
  3 1

[ 규칙 ]

출력 순서는 인수가 증가하는 순으로 한다. = 케이스 별 곱해진 횟수가 더 많은 인수 먼저

[ 백준 ]

• 에라토스테네스의 체
• 출처 : https://www.acmicpc.net/problem/2312

< 풀이 >

소수인지 아닌지 판별을 하고, 소수가 아닐 경우 몫이 1이 나올 때까지 2부터 대입하는 나눗셈을 실행한다. 0으로 나눠 떨어지는 값이 있으면 해당 값을 키로 해시 맵에 넣고, 같은 값으로 또 나눠지면 value를 증가시키는 형식으로 진행했다.
규칙의 오름차순을 위해서 키를 리스트에 다 모아 넣고, sort(Comparator.naturalOrder())로 오름차순으로 바꿔 출력하게 했다.

[ 코드 ]

import java.lang.reflect.Array;
import java.util.*;

public class BaekJoon2312 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt(); // 테스트 케이스 수
        int i,a = 0;
        ArrayList<Integer> num = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for(i=0;i<input;i++){
            num.add(sc.nextInt());
        }
        for(int n : num){
            if (Isprime(n))
                System.out.println(n + " 1");
            else{
                while (n != 1) {
                    for (i = 2; i <= n; i++) {
                        if (n % i == 0) {
                            if (map.get(i) == null)
                                map.put(i, 1);
                            else {
                                map.put(i, map.get(i) + 1);
                            }
                            break;
                        }
                    }
                    n = n/i;
                }
                List<Integer> keyList = new ArrayList<>(map.keySet());
                keyList.sort(Comparator.naturalOrder());
                for(i=0;i<keyList.size();i++){
                    System.out.println(keyList.get(i) + " "+ map.get(keyList.get(i)));
                }
                map.clear();
            }
        }
    }

    public static boolean Isprime(int num){

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

문제를 푸는 내내 풀이가 너무 지저분해서 맘에 들지 않았다. 더 깔끔하게 푸신 분과 비교해서 공부를 더 해놔야겠다.