프로그래머스
99클럽 코테 스터디 6일차 TIL 기사단원의 무기(약수 구하기)
리콜
2024. 4. 3. 22:04
오늘의 학습 키워드
약수의 갯수를 구하는 알고리즘
https://school.programmers.co.kr/learn/courses/30/lessons/136798
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제를 요약하자면 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에 대하여 공부를 해볼것이다. (배열과의 형변환이 너무 헷갈리는 겸)
- 챌린지 문제도 풀어 보고 싶다.
반응형