문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/136798

제한 사항

입출력 예

풀이
import java.util.HashSet;
class Solution {
public int solution(int number, int limit, int power) {
int answer = 0;
HashSet<Integer> countSet = new HashSet<>();
for (int i = 2; i <= number; i++) {
countSet.clear();
for (int j = 1; j <= Math.sqrt(i); j++)
if (i % j == 0) {
countSet.add(j);
countSet.add(i / j);
}
answer += (countSet.size() > limit) ? power : countSet.size();
}
return answer + 1;
}
}
후기
보통은 문제가 정 안 풀려도 최대한 힌트를 안 보려고 하는데 이 문제는 아무리 봐도 못 풀 것 같아서 약수의 개수 찾는 법을 찾아봤다. 방법은 크게 소인수 분해와 제곱근을 이용한 방법이 있는데 소인수 분해로 하면 복잡해질 것 같아서 제곱근을 이용해서 풀었다. 주어진 수의 제곱근을 구한 뒤, 그 제곱근의 약수를 구하고 해당 약수들로 원래 수를 나누어 나온 몫과 약수를 조합하면 약수의 개수를 쉽고 빠르게 얻을 수 있다. 어떤 수 N이 있을 때 제곱근 N의 약수를 구하면 그 약수들은 제곱근 N보다 작거나 같을 것이고, N의 남은 약수들은 제곱근 N보다 같거나 클 것이기 때문에 여기서 중복을 제거하면 성립하는 것 같은데 이렇게 이해한 게 맞나..?
'코딩테스트 (프로그래머스) > Java' 카테고리의 다른 글
| [프로그래머스][JAVA][Lv. 1] 완주하지 못한 선수 (0) | 2023.07.20 |
|---|---|
| [프로그래머스][JAVA][Lv. 1] K번째수 (0) | 2023.07.19 |
| [프로그래머스][JAVA][Lv. 2] 연속된 부분 수열의 합 (0) | 2023.07.17 |
| [프로그래머스][JAVA][Lv. 1] 모의고사 (0) | 2023.07.17 |
| [프로그래머스][JAVA][Lv. 2] 두 원 사이의 정수 쌍 (0) | 2023.07.17 |