[Programmers / Level1] 136798. 기사단원의 무기(Java)

💡 Info

• 난이도: Lv1
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/136798
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/1/136798. 기사단원의 무기

입출력 조건

입출력 예시

문제 이해

• 약수의 개수를 구하고, limit와 비교해 결과값이 추가해주면 되는 문제

알고리즘

풀이 시간 : 26분

• 1부터 number까지의 약수의 개수를 구해서 limit와 비교

  • 약수의 개수 > limit일 경우, power를 증가
  • 약수의 개수 <= limit일 경우, answer(약수의 개수)를 증가

• 별도 메서드 : 약수의 개수를 구하는 메서드

• 합성수 특징 이용 -> i가 제곱일일 때까지 반복하는 for문

  • 제곱근일 경우 count를 증가
  • 제곱근이 아닌 약수인 경우 count + 2로 추가하기

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for (int i = 1; i <= number; i++) {
            if (divisorCount(i) <= limit)
                answer += divisorCount(i);
            else
                answer += power;
        }
        return answer;
    }
    
    //약수 개수 메서드
    public int divisorCount(int number) {
        int count = 0;
        
        for (int i = 1; i * i <= number; i++) {
            if (i * i == number){
                count++;
            }
            if (number % i == 0) {
                count += 2;
            }
        }
        return count;
    }
}

오답체크

• 테스트 미통과 문제
  
  • divisorCount에서 각각의 if문으로 분리한 것이 원인 -> else if로 변경

//before
    public int divisorCount(int number) {
        int count = 0;
        
        for (int i = 1; i * i <= number; i++) {
            if (i * i == number){
                count++;
            }
            if (number % i == 0) {
                count += 2;
            }
        }
        return count;
    }
}

//after
    public int divisorCount(int number) {
        int count = 0;
        
        for (int i = 1; i * i <= number; i++) {
            if (i * i == number){
                count++;
            }
            else if (number % i == 0) {
                count += 2;
            }
        }
        return count;
    }
}

최종 풀이

풀이 시간 : 1시간 20분(첫 풀이 시간 포함)

• 1부터 number까지의 약수의 개수를 구해서 limit와 비교
  • 약수의 개수 > limit일 경우, power를 증가
  • 약수의 개수 <= limit일 경우, answer(약수의 개수)를 증가
• 별도 메서드 : 약수의 개수를 구하는 메서드
• 합성수 특징 이용 -> i가 제곱일일 때까지 반복하는 for문
  • 제곱근일 경우 count를 증가
  • 제곱근이 아닌 약수인 경우 count + 2로 추가하기

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for (int i = 1; i <= number; i++) {
            if (divisorCount(i) <= limit)
                answer += divisorCount(i);
            else
                answer += power;
        }
        return answer;
    }
    
    //약수 개수 메서드
    public int divisorCount(int number) {
        int count = 0;
        
        for (int i = 1; i * i <= number; i++) {
            if (i * i == number){
                count++;
            }
            else if (number % i == 0) {
                count += 2;
            }
        }
        return count;
    }
}

결과

🚨 참고할 풀이

• 1부터 시작하기 때문에, 약수는 크게 제곱수와 제곱수가 아닌 경우로 나뉨.
• j의 제곱이 i보다 작거나 같을 때까지 탐색한 후 제곱수의 경우 1번만 카운트하고 나머지 수는 2번 카운트하는 것(이전의 코드와 비슷하지만 최적화된 경우임)
• 출처 : [프로그래머스] 기사단원의 무기

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        for(int i=1;i<=number;i++){
            int cnt = 0;
            for(int j=1;j*j<=i;j++){
                if(j*j==i) cnt++;
                else if(i%j==0) cnt+=2;
            }
            
            if(cnt>limit) cnt = power;
            answer += cnt;
        }
        
        return answer;
    }
}