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

1. 문제 설명

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

 

- 제한 사항

• 1 ≤ left ≤ right ≤ 1,000

2. 풀이 코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int left, int right) {
	int answer = 0;


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

		vector<int> arr = { };


		int sqrtValue = sqrt(i);

		sqrtValue* sqrtValue == i ? answer -= i : answer += i;
		

	}


	return answer;
}

 

3. 정리

약수는 나누어 떨어지는 수가 약수 이기 때문에  약수들을 나열하면 양 끝의 약수와 서로 짝을 이룬다.

제곱근이 실수가 아닌 정수로 나오는 경우 약수들의 갯수가 홀수가 나온다.

 

ex) 16의 약수

16의 제곱근은 4이다. 따라서, 1*16, 2*8, 4*4 경우가 나오고 약수는 {1,2,4,8,16}

보통의 약수들은 짝을 이루지만 제곱근 4와 같이 정수로 떨어지는 경우는 약수를 한번만 체크하기 때문에 약수의 갯수가 홀수가 나온다 이 점을 이용한다.

 

제곱근 함수의 경우 실수형으로 반환이 된다. 이 때 int 변수에 해당 결과를 넣게 되면 소수점은 버림 처리가 묵시적으로 이루어 지기 때문에 제곱하여 원래의 수와 비교하여 다르다면 제곱근이 정수가 아니라는 것이므로 약수의 갯수가 짝수라 판단한다.

 

전체 시간 복잡도는 right-left 순회하므로  O(n) 이다.

 

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/77884