프로그래머스 - Lv1. 약수의 개수와 덧셈

문제 : 약수의 개수와 덧셈

• 문제 링크는 여기.
• 쉽게 말해, 어... 문제가 워낙 간단해서 쉽게 말할게 없다.

풀이

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        boolean isEven;

        for (int i = left; i <= right; i += 1) {
            isEven = true;

            for (int j = 1; j <= i; j += 1) {
                isEven = (i % j) == 0 ? !isEven : isEven;
            }
            answer += isEven ? i : -i;
        }

        return answer;
    }
}

• 구현 아이디어 자체는 어려울 게 없다, 문제가 원하는 대로 구해주는게 전부.

후기 : 쉽게 풀었지만, 더 잘 푸는 법이 존재했다.

1 ) 토요일 밀린 집안일을 다 하고 나니까 저녁시간이 됐길래 '아 공부는 언제 하지'했는데 너무 쉬운 문제가 나와서 좋으면서도 싫은 기분이 들었다. ;;
2 ) 다른 사람 풀이 보니까 Math.sqrt()라는 메소드로 제곱근을 구해서 약수를 찾더라. 제곱수의 경우에는 약수가 홀수(i % Math.sqrt(i) == 0)라고 풀었더라.
3 ) 저게 뭔소린데 하는 생각이 곧장 들어서 약수를 구하는 방법을 찾아보았다. N이라는 수의 약수는 제곱근을 기준으로 위 아래로 대칭되어 존재하는 성질이 있단다(오늘 말투 뭔데). 예를 들어 100의 약수를 찾는다면, 제곱근인 10을 기준으로 아래에 1, 2, 5, 총 3개의 약수가 존재하는데, 그렇다면 11~100 중에서도 3개의 약수가 존재하는 것이다.
4 ) 즉 제곱근이 자연수가 아니라면 그 위아래로 존재하는 약수의 개수는 짝수, 제곱근이 자연수라면 (짝수 + 1)개이므로 홀수가 된다. 그러면 코드는

int sqrt = Math.sqrt(i);
total += (Math.floor(sqrt) == sqrt) ? i : -i;

와 같은 식으로 작성될 것 같다(반올림 해도 그대로면 자연수. i % Math.sqrt(i) == 0보다는 위의 조건식이 수행하는 목적을 좀 더 잘 드러내는 것 같아서 바꿔봤다, 아님 말고).
5 ) 이런 똑똑한 사람들 같으니. 그리고 대량으로 소수를 구하는 '에라토스테네스의 체'라는 알고리즘이 있다는 것도 알게 되었는데, 이건 조만간 코테문제로 만날 것 같은 강력한 예감이 들므로 오늘은 설명을 패스한다.