99클럽 코테 스터디 6일차 TIL 기사단원의 무기(약수 구하기)

오늘의 학습 키워드

약수의 갯수를 구하는 알고리즘

 

https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

 

문제를 요약하자면 1~n 까지의 수 들의 약수의 갯수를 각각 구하고 limit을 초과하는 갯수인 숫자는

power로 변환하여 모두 더하는 문제 이다.

 

문제를 보자마자 1부터 n까지 나누기를 하며 나머지가 0인 숫자의 갯수를 구하는 알고리즘을 생각하고 코드를 작성하였지만 고민을 하다. 약수의 갯수를 구하는 공식 알아보았다.

 

알아보니 약수는 

제곱근이라는 중요한 공식이 있었다.

 

100의 약수를 구한다면

1, 2,4,5,10,20,25,50,100

와 같이 나오게 된다. 

구하면서 알 수 있는 점은 1 * 100 = 100 으로 1과 100이 약수가 된다.

 

100 /1 = 100

100/ 100 = 1

 

즉 한개의 약수를 구하게 된다면 다른 약수가 자동으로 지정이 되는 것이다.

 

이때 중간점이 되는 값이 제곱근의 수, 즉 n의 루트 이다.

 

10을 기점으로 1과 100, 2와 50, ..

이 구해지게 되므로 제곱근의 수까지 약수의 갯수를 구한뒤 x2를 하면되는 것이다.

그 후 제곱근의 숫자의 갯수까지 더하면 된다.

 

 

이에 배운 내용을 바탕으로 코드를 작성 하였다.

sqrt를 사용해도 될것 같다.

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        //약수 갯수를 구하고 limit과 비교후 처리
        for(int i = 1; i <= number; i++){
            int temp = getPower(i);
            if(temp > limit){
                temp = power;
            }
            answer += temp;
        }
        return answer;
    }
    
    //약수의 갯수를 구하는 함수
    public int getPower(int num){
        int count = 0;
        for(int i = 1 ; i * i <= num ; i++){
            if(i * i == num){
                count++;
            }
            else if(num % i == 0){
                count += 2;
            }
        }
        return count;
    }
}

 

 

내일 공부할 내용

 

내일 공부할 내용

• 내일은 ArrayList에 대하여 공부를 해볼것이다. (배열과의 형변환이 너무 헷갈리는 겸)
• 챌린지 문제도 풀어 보고 싶다.