[프로그래머스 LV.1] #23 약수의 개수와 덧셈 (JavaScript)

💡 문제

약수의 개수

 

🔍 분석 및 계획

✅ 문제 이해

두 정수가 주어질때, 두 정수 사이의 모든 수 중에서 약수의 개수가 짝수인 수는 더하고 홀수인 수는 더한 값을 반환

• 입력 값 : 두 정수
  - 1 <= 정수1 <= 정수2 <= 1,000 
• 출력 값 : 계산 값

계산값을 저장할 변수 한개와 내부에 약수의 개수를 구하는 식만 있으면 쉽게 구현할 수있다

 

✅ 의사코드 작성

계산값을 저장할 변수생성
for(작은수 to 큰수)
	약수의 개수 계산
    if(약수의 개수가 짝수) 변수에 더하기 
    else 변수에서 빼기
계산값 반환

 

 

📝 코드 구현

의사코드 + 코드

function solution(left, right) {
  //계산값을 저장할 변수생성
  let answer = 0;
  //for(작은수 to 큰수)
  for (let i = left; i <= right; i++) {
    //약수의 개수 계산
    let cnt = 0;
    for (let j = 1; j * j <= i; j++) {
      if (j * j === i) cnt++;
      else if (i % j === 0) cnt += 2;
    }
    //if(약수의 개수가 짝수) 변수에 더하기
    if (cnt % 2 === 0) answer += i;
    //else 변수에서 빼기
    else answer -= i;
  }
  //계산값 반환
  return answer;
}

 

최종 코드

function solution(left, right) {
  let answer = 0;
  for (let i = left; i <= right; i++) {
    let cnt = 0;
    for (let j = 1; j * j <= i; j++) {
      if (j * j === i) cnt++;
      else if (i % j === 0) cnt += 2;
    }
    if (cnt % 2 === 0) answer += i;
    else answer -= i;
  }
  return answer;
}

시간 복잡도 : O(1) ~ O(n)

=> O(n) ~ O(n²)  (n의 제한이 없을시)

 

💭 되돌아 보기

✅ 개선점

 

✅ 다른 사람 풀이

 

1.
제곱근이 정수면 약수의 개수가 홀수가 됨을 이용한 코드.. 아이디어의 세계다

function solution(left, right) {
    var answer = 0;
    for (let i = left; i <= right; i++) {
        if (Number.isInteger(Math.sqrt(i))) {
            answer -= i;
        } else {
            answer += i;
        }
    }
    return answer;
}