(알고리즘) 백준 2312 - 수 복원하기

문제

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

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다.

출력

각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.

예제 입력 1

2
6
24

예제 출력 1

2 1
3 1
2 3
3 1

풀이

먼저, 변수 j를 2부터 차례대로 더하여 HashMap에 <해당 숫자, 나뉘어진 횟수> 형태로 담는다.
그리고 주어진 숫자가 while문 안에서 j에 나누어 떨어질 경우, 나눈 후에 value(나뉘어진 횟수)를 증가시킨다.

이렇게 하면 2부터 차례대로 숫자와 나뉘어진 횟수가 map에 담길 것이다.

그리고 마지막 forEach문에서 소인수 검증을 수행한다.

해당 숫자(key)의 value가 0인 경우에는 소수가 아니거나 약수가 아닐 것이다.
이 때, 소인수분해의 결과는 소수로만 이루어져야 하기 때문에 소수이면서 약수여야 한다.

따라서 value가 0인 경우를 제외하고, 각각 key와 value를 출력해주면 된다.

처음에는 주어진 숫자를 2부터 증가시켜 차례대로 나누며 소수 판별을 진행했는데, 시간초과에 걸렸다.
이 풀이 방법으로 통과는 했지만 더 나은 방법을 찾아봐야겠다.