[백준 1241] 머리 톡톡 - JAVA

BOJ Link

https://www.acmicpc.net/problem/1241

 

 

풀이 과정

입력을 배열에 저장함과 동시에, 각 숫자를 가진 사람의 개수 cnt를 map에 같이 merge해준다.

이후 배열을 순차탐색하며, i번째 원소의 약수의 cnt를 모두 더한 값 sum을 구해준다.

 

이때,

해당 원소의 sum을 구한적이 없다면, 구하여 result map과 stringbuilder에 저장한다.

구한적이 있다면, result map의 값을 사용하여 stringbuilder에 저장한다.

 

탐색을 마쳤다면 출력한다.

 

핵심 아이디어는 다음과 같다.

 

1. 어떤 자연수 M의 약수를 N이라고 하면,

M의 N집합을 구하기 위해 1 ≤ N ≥ sqrt(M)이하인 범위만 탐색하면 된다.

 

2. 어떤 N이 존재한다면, N * M/N = M이다. 따라서,

N != M/N라면, 각각의 cnt를 map에서 찾아 sum에 더한다.

N == M/N라면, 중복 계산을 피하기 위해 N의 cnt만 sum에 더한다.

 

3. 자기 자신은 제외하기 위해 sum--; 해준다.

제출 코드

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

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < N; i++) {
            int e = Integer.parseInt(br.readLine());
            arr[i] = e;
            map.merge(e, 1, (ov, nv) -> ov + 1);
        }

        Map<Integer, Integer> result = new HashMap<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            int now = arr[i];
            if (result.containsKey(now)) sb.append(result.get(now)).append("\n");
            else {

                int divVal = 1;
                int sqrt = (int) Math.sqrt(now);
                int sum = 0;

                while (divVal <= sqrt) {
                    if (now % divVal == 0) {

                        if (divVal == now / divVal) {
                            sum += map.getOrDefault(divVal, 0);
                        } else {
                            sum += map.getOrDefault(divVal, 0);
                            sum += map.getOrDefault(now / divVal, 0);
                        }
                    }
                    divVal++;
                }
                sum--;
                sb.append(sum).append("\n");
                result.put(now, sum);
            }
        }

        System.out.println(sb);
    }
}