JAVA 알고리즘 - 약수의 개수와 덧셈 뺄셈


문제 설명

두 정수 left와 right가 매개변수로 주어집니다.

left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고,

약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.


제한사항

1 ≤ left ≤ right ≤ 1,000


입출력 예

leftrightresult
131743
242752

문제풀이

약수의 갯수를 구하는 방법은, 1을 포함한 해당 수까지의 값을 나눠서 나머지가 0인 수를 구하면 됩니다.
해당 수의 제곱근을 나눠서 나머지가 0인 수는 홀수, 그렇지 않으면 짝수의 갯수로 구할 수 있습니다.
Math.sqrt 함수를 이용해서 제곱근을 구할 수 있으니, 아래 소스를 참고해서 풀어보시기 바랍니다.

O(n^2) 소스와 O(1) 또는 O(log N) 알고리즘 입니다.

  1. import java.util.*;
  2. class Solution {
  3. public int solution(int left, int right) {
  4. int answer = 0;
  5. // O(n^2)
  6. /*
  7. for ( int i=left; i<=right; i++ ){
  8. int cnt = 0;
  9. for ( int j=1; j<=left; j++){
  10. if ( i % j == 0){
  11. cnt++;
  12. }
  13. }
  14. if (cnt % 2 == 0){
  15. answer += i;
  16. } else {
  17. answer -= i;
  18. }
  19. left++;
  20. }
  21. */
  22. for (int i=left; i<=right; i++){
  23. // 제곱수로 나눴을 때 나머지가 0이면 홀수
  24. if ( i % Math.sqrt(i) == 0 ){
  25. answer -= i;
  26. } else {
  27. answer += i;
  28. }
  29. }
  30. return answer;
  31. }
  32. }



* 파트너스 활동을 통해 일정액의 수수료를 제공받을 수 있음
작성자 소개
최찬희 프로필
WrapUp 블로거

최찬희

반려견을 좋아하고, 차를 좋아하고, 여행을 좋아하고, 맛집을 찾아 즐기는 웹 개발자 입니다^^

댓글작성

관련 블로그 구경하기

작성자의 다른 포스팅