[알고리즘] 프로그래머스 : 약수의 합

알고리즘 문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/12928

프로그래머스

 

내가 작성한 코드

약수를 구하는 거니까 나눠서 나머지가 0이 되는 데서 찾았다. 다른 사람들의 코드를 봤는데 다 비슷비슷했던 문제. 

class Solution {
  public int solution(int n) {
      int answer = 0;
      for(int i = 1; i < n + 1; i++){
          if(n % i == 0)
              answer += i;
      }

      return answer;
  }
}

 

하지만 이 코드를 보고 충격받음. 내 코드랑 거의 비슷한데 절반 밖에 돌리지 않아서 효율적이다.

생각해보니까 약수 구할 때 다 돌릴 필요가 없다. 절반만 돌리면 된다. 모든 수는 1과 자기 자신을 약수로 가지고, 그리고 그 다음에는 가장 작은 소수인 2부터 시작해서 나눠서 약수인지 아닌지 알아볼 수 있다. 그러니 1부터 시작해서 자기 자신을 2로 나눈 값까지만 돌려도 웬만한 약수를 다 구할 수 있고 누락된 자기 자신은 마지막에 더해줘도 되는 것이다.

class SumDivisor {
    public int sumDivisor(int num) {
        int answer = 0;
        for(int i = 1; i<=num/2; i++){
			if(num%i==0){
        	answer+=i;
      		}
    	}
        return answer+num;
    }

 

프로그래밍에 있어서 수학이 굉장한 무기가 될 수 있다는 걸 다시 한번 깨닫는다. 깔끔하고 효율적인 코드를 짜기 위해 계속 고민하고 성장해가야겠다.