2024년 11월 11일(월) Today I Learned

약수의 개수와 덧셈

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

해당 문제는 주어진 수들의 약수의 개수의 홀짝을 판별하는 간단한 문제이다. 처음 구현했던 코드에서는 단순히 for문으로 약수를 하나씩 확인하여 홀짝을 판별하였다.

 

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        for (int i = left; i <= right; i++) {
            int count = 1;
            for (int j = 1; j <= i/2; j++) {
                if (i % j == 0) {
                    count++;
                }
            }

            if (count % 2 == 0) {
                answer += i;
            } else {
                answer -= i;
            }
        }
        return answer;
    }
}

 

 

문제의 난이도는 쉬웠기에 쉽게 통과할 수 있었다. 하지만 효율성 부분이 좀 떨어지는 느낌을 받았다.

 

 

사실 약수의 개수를 굳이 구할 필요가 없었다. 약수의 홀짝의 비밀을 알아채면 더 쉽고 효율적으로 코드를 구현할 수 있다. 어느 한 수를 number라 하고 a * b = number라 할 때, a와 b는 number의 약수라 할 수 있다. 즉 기본적으로 약수는 짝을 이루기에 대부분의 수들은 약수를 짝수로 갖는다. 하지만 a * a = number인 수, 제곱수인 수가 짝을 이루지 않는 수를 약수로 갖기에 약수의 개수가 홀수로 갖는다. 따라서 주어지는 수가 제곱수인지만 확인하면 효율적으로 풀어나갈 수 있다.

 

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        for (int i = left; i <= right; i++) {
            if (i % Math.sqrt(i) == 0) {
                answer -= i;
            } else {
                answer += i;
            }
        }

        return answer;
    }
}

 

 

문제를 너무 정석적으로만 생각하지 말고, 문제의 근본적인 요점을 파악하는 것이 중요한 문제였다