알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.
Problem📄
https://school.programmers.co.kr/learn/courses/30/lessons/136798
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
Think🤔
약수를 구하는 방법이 이 문제의 핵심포인트
약수를 효율적으로 구해야지 100,000까지 반복문을 돌면서 시간이 많이 안걸리게 할 수 있다.
Solution✍
class Solution {
public int solution(int number, int limit, int power) {
int answer = 0;
int tmp = 1;
for(int i=1; i<=number; i++){
tmp = measure(i);
if(tmp > limit){
answer += power;
}else{
answer += tmp;
}
}
return answer;
}
public int measure(int x){
int count = 0;
int sqrtX = (int) Math.sqrt(x); // x의 제곱근 계산
for (int i = 1; i <= sqrtX; i++) {
if (x % i == 0) {
count += 2; // i와 x/i 두 개의 약수를 찾음
}
}
// 완전제곱수의 경우 중복으로 센 약수 하나를 뺌
if (sqrtX * sqrtX == x) {
count--;
}
return count;
}
}
// number의 약수를 구하는 부분이 핵심
// Math.sqrt(number);를 이용한다. 100,000까지의 약수를 구하면 시간이 너무 오래걸려서 돌지 않을것..
Review🤩
100 1 2 5 10 20 50 100 -> 7개
10 1 2 5 10 -> 4개
25 -> 3개
5 -> 2개
400 -> 1 2 4 5 8 10 20 40 50 80 100 200 400 -> 13
20 -> 1 2 4 5 10 20 -> 6개
처음에 이런식으로 규칙을 찾았는데 해당 방법이 맞지 않음
25 같은 경우 완전수
sqrt는 제곱근으로 두 개의 약수를 찾은 후 완전수 인 경우 1 , 5 , 5 , 25 으로 5가 두번 들어가기 때문에 1개를 빼줘야 한다.
'Algorithm' 카테고리의 다른 글
[프로그래머스] 옹알이2 (0) | 2023.10.17 |
---|---|
[프로그래머스] 코딩테스트 연습연습문제덧칠하기 (1) | 2023.10.17 |
[프로그래머스] 코딩테스트 연습연습문제카드 뭉치 (0) | 2023.10.16 |
[프로그래머스] 코딩테스트 연습연습문제추억 점수 (0) | 2023.10.16 |
[프로그래머스] 명예의 전당 (1) (0) | 2023.01.02 |