[자바] 백준 1241 - 머리 톡톡 (boj java)

문제 : boj1241

 

  에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유(글 링크) 이 글을 이해했다면 쉽게 풀 수 있다. N개를 입력받으면서 HashMap 등으로 각 숫자의 존재 여부 및 몇 개 존재하는지 저장해둔다.

 

  이후 N개를 순회하면서 각각을 A라고 하면, 1부터 sqrt(A) 사이에 존재하는 A의 약수가 B라 하자. 그럼 HashMap에서 B의 개수를 더해주고, A/B도 약수일 것이므로 그것도 HashMap에서 찾아 더해주면 된다. 이 때 주의점은 sqrt(A)로 A가 나누어 떨어질 경우 (즉, (int)sqrt(A) * (int)sqrt(A) == A 인 경우), 두 번 더해지게 되므로 한 번은 빼줘야 한다.

 

  그럼 시간복잡도는 N명 중 가장 큰 숫자가 K라 할 때, O(N*sqrt(K)) 가 된다. 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> hm = new HashMap<>();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(br.readLine());
            arr[i] = cur;
            hm.put(cur, hm.getOrDefault(cur, 0) + 1);
        }
        int[] cnt = new int[n];
        for (int i = 0; i < n; i++) {
            int cur = arr[i];
            int limit = (int)Math.sqrt(cur);
            cnt[i] = limit*limit==cur?-hm.getOrDefault(limit, 0):0;
            for (int j = 1; j <= limit; j++) {
                if (cur%j!=0) continue;
                cnt[i] += hm.getOrDefault(j, 0) + hm.getOrDefault(cur/j, 0);
            }

        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(cnt[i]-1).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}