[프로그래머스] 약수의 개수와 덧셈 (Lv.1)

---

문제 링크

---

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

문제 설명

---

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

제한사항

• 1 ≤ left ≤ right ≤ 1,000

내 풀이

---

left부터 right까지 각 수를 순회하며, 1부터 해당 수까지 나누어 약수의 개수를 센다. 약수 개수가 짝수면 answer에 더하고, 홀수면 뺀다.

#include <string>
#include <vector>

using namespace std;

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

    for(int i = left; i <= right; i++)
    {
        int count = 0;
        for(int j = 1; j <= i; j++)
        {
            if(i % j == 0) count++;
        }
        
        if(count % 2 == 0)
        {
            answer += i;
        }
        else
        {
            answer -= i;
        }
    }
    
    return answer;
}

시간복잡도 분석

---

• 외부 루프: O(right - left + 1) ≤ O(1,000)
• 내부 루프 (약수 탐색): O(i) ≤ O(1,000)
• 전체: O(N²), N = right - left + 1 (최대 1,000)

최대 약 1,000,000번 연산 → 충분히 통과 가능하다.

후기

---

• algorithm
• codingtest
• bruteforce