[프로그래머스] 기사단원의 무기 + 약수 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

해당 문제의 핵심은 약수의 개수를 찾는 것이다.

하지만 단순하게 시간복잡도 때문에 단순하게 약수를 찾으면 시간초과가 떠버린다.

 

1. 단순하게 모든 수를 나눠서 약수 구하기

List<Integer> getDivisor(int N){
        List<Integer> divisors = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            if (N%i==0)divisors.add(i);
        }
        return divisors;
    }

가장 일반적으로 생각하는 약수 구하는 방법이다.

1부터 주어진 수 까지 반복해가면서 나머지가 0 인 값들을 구해주는 것이다.

하지만 역시 이런 식으로 구현을 한다면 시간 복잡도에 있어 그렇게 좋은 코드는 아니다.

좀 더 다양한 방법에 대해 배워보자.

 

 

 

2. 주어진 수의 절반을 대상으로만 확인하기

   List<Integer> getDivisor(int N){
        List<Integer> divisors = new ArrayList<>();
        for (int i = 1; i <= N/2; i++) {
            if (N%i==0)divisors.add(i);
        }
        divisors.add(N);
        return divisors;
    }

아주 간단한 논리이다. 약수는 본인을 제외하고 n/2 보다 클 수 없기 때문에 절반값까지만 체크를 해주는 것이다.

이렇게만 해도 1번 예제보다 더 좋은 성능을 낼 수 있다.

 

이제 여기까지 왔으면 다음에 뭐가 나올지 어느 정도 예상이 가능한데,

소수 판별 알고리즘과 마찬가지로 제곱근을 활용할 수 있다.

 

 

3. 제곱근 사용하기(★)

 List<Integer> getDivisor(int N){
        List<Integer> divisors = new ArrayList<>();
        for (int i = 1; i <= Math.sqrt(N); i++) {
            if (N%i==0){
                divisors.add(i);
                if (N/i != i)divisors.add(N/i);
            }
        }
        return divisors.stream().sorted().collect(Collectors.toList());
    }

제곱근을 이용하는 방식은 좀 이해가 필요하다.

 

num을 100이라고 가정하자.

Math.sqrt(100) = 10이라는 값이 도출된다.

 

그러면 어떻게 10까지만 숫자를 체크하는데 나머지 약수 값들을 구할 수 있는 걸까?

코드를 보면 알겠지만 해당 약수를 가지고 입력받은 값을 나누게 될 경우 나오는 결과 값 역시 약수이기 때문이다.

100의 약수를 10 이하의 숫자만 나열하면 [1, 2, 4, 5, 10]이다.

 

하나씩 나누어 본다면

100 / 1 = 100

100 / 2 = 50

100 / 4 = 25

100 / 5 = 20

100 / 10 = 10

 

10이라는 숫자가 중복되기 때문에 N/i!= i 일 때라는 조건을 걸어야 한다.

 

위의 불필요한 코드를 수정할 수도 있긴하다.

 

Set<Integer> getDivisor(int N){
        Set<Integer> divisors = new TreeSet<>();
        IntStream.rangeClosed(1,(int)Math.sqrt(N)).filter(i -> N%i==0)
                .forEach(i -> {divisors.add(i); divisors.add(N/i);});
        return divisors;
    }

TreeSet을 사용하여 중복제거 및 정렬을 한 번에 할 수 도있다.

 

정답 코드

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for (int i = 1; i<= number; i++){
            int count = 0;
            for (int j = 1; j<= Math.sqrt(i); j++){
                if (i%j == 0){
                    count++;
                    if (i/j != j)count++;
                }
                if (count>limit){
                    count = power;
                    break;
                }
            }
            answer+=count;
        }
        return answer;
    }
}

 

해설

문제를 단순하게 해석해 보면, 1~number까지 약수의 개수를 구한다.

그때의 약수의 개수가 limit을 넘기면 지정된 기본값으로 대체된다.

이를 모두 더한다. 

단순하게 풀면 시간복잡도에서 걸리기 때문에 제곱근을 활용해야 한다.

 

배운 점

제곱근을 사용하여 푼다는 것이 매우 인상적이었고, 

쉬운 문제였지만 이러한 개념을 생각하지 못한다면, 풀기 힘들 것이라 생각했다.

제곱근과 같은 풀이법은 익혀두는 것이 큰 도움이 될 것 같다.