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

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문제 출처

코딩테스트 연습 - 약수의 개수와 덧셈

[문제 설명]

left부터 right까지 각각의 약수의 개수를 구합니다.

각각의 약수의 개수가 홀수이면 빼고 짝수이면 더합니다.

 

[처음 생각한 접근 방법]

어차피 약수면 1부터 숫자의 절반까지만 가도 약수의 전체를 구할 수 있습니다. (사실 루트 씌운 값까지만 가면 된다.)

14이면 7까지만 가도, {1,13},{2,7}로 모든 개수를 구할 수 있습니다.

문제는 16과 같이 {1,16},{2,8},{4,4}인 경우 4는 1개만 추가 됩니다.

중복을 허용하지 않는 set을 이용하여 size를 구하는 방법도 있겠지만 이번엔 그냥 if 조건을 따로 둬서 처리했습니다.

class Solution {
    public int solution(int left, int right) {
    	//약수의 총합
        int answer = 0;
        //left가 right가 될 때까지 반복.
        while (left <= right) {
        	//이번 수의 약수의 개수.
            int numOfDivisor = 0;
            //1부터 left절반 +1까지 (1의 예외를 위해)
            for (int j = 1; j <= left/2 + 1; j++) {
            	//약수이면,
                if (left % j == 0) {
                	//두 약수의 값이 같으면.(16에 4,4)
                    if (left/j == j) numOfDivisor += 1;
                    //두 약수의 같지 않으면. (16에 2,8)
                    else numOfDivisor += 2;
                }
            }
			//약수의 개수가 짝수면 더하고
            if (numOfDivisor % 2 ==0) answer += left;
            //약수의 개수가 홀수면 뺀다.
            else answer -= left;
            //left는 값을 더해서 전진.
            left++;
        }

        return answer;
    }
}

루트를 활용했을 경우,

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        while (left <= right) {
            int numOfDivisor = 0;
            int leftSqrt = (int)Math.sqrt(left);
            for (int i = 1; i <= leftSqrt; i++) {
                if (left % i == 0) {
                    if (left/i == i) numOfDivisor += 1;
                    else numOfDivisor += 2;
                }
            }

            if (numOfDivisor % 2 ==0) answer += left;
            else answer -= left;
            left++;
        }

        return answer;
    }
}