[프로그래머스/Lv. 1] 기사단원의 무기

🔺 문제

프로그래머스

 

🔺 코드

- 틀림

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0; // 철 무게
        int[] arr = new int[number+1];
        
        // 약수 구하기
        for(int i = 1 ; i <= number ; i++) {
            for(int j = 1 ; j <= i ; j++) {
                if(i % j == 0) {
                    arr[i]++;
                }
            }            
        }

        for(int i : arr) {
            if(i <= limit) {
                answer += i;
            } else {
                answer += power;
            }
        }
        
        return answer;
    }
}

배열을 만들어서 이 안에 약수 갯수 정보를 담고,

이 약수 갯수 배열이 값이 limit보다 작거나 같으면 약수 갯수를 더하게 하고,

크면 power를 더하게 하려고 했는데 시간 초과가 떴다.🤦‍♀️😓

 

고로 약수 구하는 부분을 수정해야 했다.

 

- 정답

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0; 	// 철 무게
        
        // 1부터 number까지 약수 개수 구하기
        for(int i = 1 ; i <= number ; i++) {
            int cnt = 0; 	// 약수 개수
            
            // i의 약수를 찾기 위해 1부터 sqrt(i)까지 반복
            for(int j = 1 ; j <= (int)Math.sqrt(i) ; j++) {
                if(i % j == 0) { 	// j가 i의 약수인 경우
                    cnt += 2; 		// j와 i/j를 각각 두 개씩 카운트
                    
                    if(j * j == i) { 	// j가 정확한 제곱근인 경우
                        cnt--; 		// 중복 카운트 방지
                    }
                }
            }  
            
            if(cnt <= limit) {
                answer += cnt; 
            } else { 	
                answer += power; 
            }
        }
        
        return answer;
    }
}

💥 유의사항 →  j의 범위 : Math.sqrt(n)

반복문 j의 범위!가 중요한데 i가 아니라 (int) Math.sqrt(i), 즉 제곱근까지 반복문을 돌려주고,

이 안에서 if문으로 약수인지 확인한다.

만약 약수라면, 약수가 (i, i/j) 2개 짝으로 생기니까 cnt에 +2.

그리고 j가 정확한 제곱근인 겨우, 중복 카운트 방지를 위해 --를 해준다.

 

그리고 여기서 탈출해서, 약수 개수가 limit 이하인 경우와 초과인 경우를 구분하여 철의 무게를 계산하면 된다...

 

 

---

🔺 다른 풀이들

프로그래머스

class Solution {

    public int solution(int number, int limit, int power) {
        int[] count = new int[number + 1];
        
        for (int i = 1; i <= number; i++) {
            for (int j = 1; j <= number / i; j++) {
                count[i * j]++;
            }
        }
        
        int answer = 0;
        
        for (int i = 1; i <= number; i++) {
            if (count[i] > limit) {
                answer += power;
            } else {
                answer += count[i];
            }
        }
        return answer;
    }
}

count 배열 안에 넣는 값을 i * j로 하셨다.

---

💬 느낀 점

약수 문제는 이제 빠삭하다고 생각했는데 또 오랜만에 푸니 까먹고...

그렇게 되었다....