프로그래머스 LV1 - 기사단원의 무기

해당 문제도 아무것도 모르던 시절 시도해봤던 문제다.

이 문제의 핵심은 약수들을 찾을때 반복 범위를 최소화 할것.

 

하나의 숫자 x 의 약수들은 반드시 짝을 이루며 인수1 로 숫자를 나누면 인수2를 찾을 수 있다.

이를 통해 탐색범위를 절반으로 한번 줄일 수 있고,

5*5 = 25 와 같이 인수1,2 가 제곱근으로 같은 경우가 있다면

그 이후론 이미 구한 값들만 반복될 것이기 때문에 탐색할 이유가 없다.

그래서 탐색범위를 숫자 x의 제곱근 까지로 한번 더 줄일 수 있다.

 

숫자 x의 제곱근 까지 탐색하며 약수를 찾고, 인수1과 인수2를 한번에 찾는다.

그리고 중복을 허용하지 않는 Set을 이용해 인수1과 2가 같은경우 ( 제곱근 ) 을 쉽게 관리한다.

또한 Set.size()가 limit 보다 커진경우 더 이상 계산은 불필요하기때문에,

break로 해당 반복문을 즉시 빠져나온다.

 

import java.util.*;
    
class Solution {
    public int solution(int number, int limit, int power) {
        
        int answer = 0;
        
        for (int start = 1; start <= number; start++) { // 모든 number 반복
            Set<Integer> set = new HashSet<>();
            int currentAnswer = 1;
            for (int current = 1; current <= Math.sqrt(start); current++) { // start의 제곱근까지만 계산.
                
                if(start % current == 0){ // 약수인 경우
                    set.add(current);		// 인수1 set에 담기
                    set.add(start / current);	// 인수2 set에 담기
                    currentAnswer = set.size();	// 현재 number의 답 갱신
                }
                
                if(set.size() > limit){		// limit보다 큰 경우
                    currentAnswer = power;	// power로 변경
                    break;		// for 종료.
                }
            }
            answer += currentAnswer;		// 각 number의 해답 합산
        }
        
        return answer;
    }
}

 

 

조금씩 조금씩 착실히 늘고있는 느낌 쏘굿. 느좋.