[백준 1241번] 머리 톡톡

 

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

 

 

 

 

문제의 핵심

1. 자신이 쓰고 있는 숫자가 다른 사람이 쓰고 있는 모자의 배수라면 count 해준다.
2. 동일한 숫자를 쓰고 있는 학생의 수가 있을 수 있다.

 

arr[] : 해당 위치에 적혀있는 모자의 숫자

Map<Integer, Integer> map : 현재 모자에 적혀져있는 숫자들의 개수 -> 적혀있는 숫자들의 모자들을 함께 counting

cnt[] : 해당 위치에서 자신이 머리를 친 학생의 수를 더한다.

 

배열을 돌면서 현재 자신의 모자에 적힌 숫자에 약수를 구한 후, 약수에 적힌 다른 사람이 쓰고 있는 모자의 번호의 개수(map의 value) 만큼 counting해서 더해준다.

 

만약 4의 약수의 경우 1,2,4인데 -> 여기서 2 * 2는 같은 숫자이므로 동일한 약수의 경우 counting을 하나 제외해줘야 한다.

 

약수를 구할 때에도 Math.sqrt를 하여 시간복잡도를 줄이고, Math.sqrt()로 햇을 때 나온 숫자가 현재 적혀 있는 모자의 숫자를 나눴을 때 나머지가 0이라면 해당하는 숫자와 curr / j를 했을 때 나오는 숫자는 약수의 쌍이므로 해당하는 모자의 개수만큼 더해주면 된다.

 

import java.util.*;
import java.io.*;

public class BOJ_G5_1241_머리톡톡 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		// 해당 위치에 적혀있는 모자의 숫자
		int[] arr = new int[N];
		// 현재 모자에 적혀져있는 숫자들의 개수
		Map<Integer, Integer> map = new HashMap<>();

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
			map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
		}

		int[] cnt = new int[N];

		for (int i = 0; i < N; i++) {
			int curr = arr[i];
			int sq = (int) Math.sqrt(curr);

			// 동일한 약수인 경우 하나만 나와야한다.
			if (sq * sq == curr) {
				cnt[i] -= map.getOrDefault(sq, 0);
			} else {
				cnt[i] = 0;
			}

			for (int j = 1; j <= sq; j++) {
				if (curr % j == 0) {
					cnt[i] += map.getOrDefault(j, 0) + map.getOrDefault(curr / j, 0);
				}
			}
		}

		for (int i = 0; i < N; i++) {
			sb.append(cnt[i] - 1).append('\n');
		}

		System.out.println(sb);

	}
}