Problem

https://school.programmers.co.kr/learn/courses/30/lessons/120836

Solution

brute force를 사용해도 O(n) 성능만에 풀 수 있는 문제다.

Miss

난 처음에 Hashset을 이 문제에 적용하고 나 자신을 뿌듯해 했으나, 이틀 뒤에 문제를 포스팅하려고 복습하니 필요없는 과정이었다는 걸 깨달았다.

Optimal

원래 난 풀리면 그 문제는 그 이상의 최적화를 찾지 않는다. 근데 이건 순서쌍 개념으로서 알고 넘어가면 좋겠다 싶어서 적는다. 그냥 슥 읽어만 본다.

👉 “약수는 √n 기준으로 좌우 대칭이다”

⚠️ 예외 (완전 중요)
👉 i * i == n인 경우 (완전제곱수) >> 예:16 → (4,4)
👉 이건 하나만 세야 함
그래서: if (i * i == n) 분기 필요

Code

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

optimal (최적화)

class Solution {
    public int solution(int n) {
        int answer = 0;

        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                if (i * i == n) {
                    answer++;      // 예: 4 * 4
                } else {
                    answer += 2;   // (i, n/i)
                }
            }
        }

        return answer;
    }
}