프로그래머스) 기사단원의 무기 Lv1

1래밸 문제들 중 손풀기용으로 정답률이 높은 문제를 풀었다!

 

약수의 갯수를 구하고 제한 숫자가 넘으면 해당 숫자로 변경해야하는 문제

 

약수를 구하는 방법이 생각이 나질않아 구글링해볼까.... 하다가

그럼 안되지! 하고 열심히 고민을 해서 풀어보았다

 

후다닥 풀고 슬적 기대하면서 코드 실행을 해봤는데

테스트1 통과 테스트2 실패

 

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

 

아무리봐도 문제가 없는데.... 

확인해보니 제한사항을 빠트렸다 ㅎㅎ;

 

후다닥 제한사항을 넣었는데 코드가 조금 더럽네

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

 

테스트는 문제없이 통과했지만 제출해보니....

첫 시간 초과 실패가 떴다;

소스가 더러운 느낌이 있어서 실패하지않을까 했는데 시간초과가 떴다 ㅎㅎ

 

약수를 구하는 과정이 시간을 너무 많이 먹어버리는 것 같았다

어쩔 수 없이 구선생(구글)의 도움을 받기로 했다~

 

java 약수개수 구하는 최적의 알고리즘 방법에 대해서 검색해보니 다양한 방법들이 나와있었다

 

그 중 촨님의 블로그를 참고했는데 약수를 구하는 2가지 방법이 있었다

나는 위 문제를 방법 1로 풀어서 시간 초과가 났는데, 방법 2로 풀면 실행시간이 훅! 줄어들어버린다...

 

흠.. 약수를 구하는 코드는 그냥 외우는게 맘이 편할 것 같다 ㅎㅎㅎ

 

 

---

정답

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int cnt = 0;
        
        for(int i=1; i<=number; i++){
            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;
            cnt = 0;
        }
        
        return answer;
    }
}

 

 

 

출처

촨님의 블로그 - https://chwan.tistory.com/entry/Java-%EC%95%BD%EC%88%98%EC%9D%98-%EA%B0%9C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0

프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/136798

1. 기사단원의 무기
2.  

•