프로그래머스 약수의 합 (99클럽 코딩테스트 20일차 TIL)

목표

알고리즘 공부한지 20일차인데 이렇게 문제가 간단한건 이제 조금만 생각해도 큰방이 답이 나오는것같다. 앞으로 문제 설명 길이가 조금더 긴 문제를 풀었을때 바로 적응하는게 목표이다.

문제

내가 생각했을때 문제에서 원하는부분

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수

내가 이 문제를 보고 생각해본 부분

1. n을 입력받는다.
2. n의 약수를 모두 더한다. 
3 return 해준다.

코드로 구현

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

시간복잡도는 O(N)
for문에서 1부터 N까지의 모든 수를 확인하므로 O(N) 시간복잡도를 사용했다.

장점
입력값 N에 대해 선형적으로 수행시간이 증가하므로 효율적이다.
구현이 간단하다.

단점
N이 커지면 연산 횟수가 기하급수적으로 늘어난다.
다만 이 문제의 경우 N의 크기가 최대 500으로 비교적 작다고 가정할 수 있습니다.
모든 약수를 찾아야 하므로 최적화할때 비효율적이다.

마무리

오늘 문제 역시 간단하게 풀수 있는 문제였다. 문제를 20일 정도 풀다보니깐 기본적인 문제는 접근을 어떻게 해야하는지 조금 감이 오는것같다. 생각하고 코딩하는데 조금 시간이 걸릴뿐, 이제 문제 설명이 조금더 긴 문제를 풀때 조금더 수월하게 문제를 풀었으면 좋겠다.