[프로그래머스][JAVA][Lv. 1] 기사단원의 무기

문제 설명

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보다 같거나 클 것이기 때문에 여기서 중복을 제거하면 성립하는 것 같은데 이렇게 이해한 게 맞나..?