BOJ 1241 - 머리 톡톡

문제

N명의 학생이 각각 번호를 가지고 있을 때, 각 학생에 대해 자신의 번호의 약수를 번호로 가진 다른 학생 수를 구하라.

입력

첫째 줄에 N, 이후 N줄에 각 학생의 번호가 주어진다.

출력

각 학생에 대해 자신의 번호를 톡톡하는 학생 수를 출력한다.

예제

입력	출력
`3` `2` `4` `6`	`0` `1` `1`

풀이

카운팅 배열로 번호 빈도를 기록하고, 배수 열거로 각 번호의 약수 카운트를 계산한다.

각 번호의 등장 횟수를 카운팅 배열에 기록한다
번호 i에 대해 i의 배수인 번호들의 hit 값에 cnt[i]를 누적한다
같은 번호끼리는 자신을 제외해야 하므로 cnt-1을 더한다
각 학생의 번호에 해당하는 hit 값을 출력한다

핵심 아이디어: 배수 열거로 모든 약수 관계를 O(M log M)에 처리하여, 학생 수가 많아도 효율적으로 해결한다.

코드

const solution = (input) => {
  const MAX_SIZE = 1_000_000;
  const cnt = new Array(MAX_SIZE + 1).fill(0);
  const hit = new Array(MAX_SIZE + 1).fill(0);
  let ans = "";
 
  for (let i = 1; i < input.length; i += 1) {
    cnt[input[i]] += 1;
  }
 
  for (let i = 1; i <= MAX_SIZE; i += 1) {
    if (cnt[i] === 0) continue;
    hit[i] += cnt[i] - 1;
    for (let j = i * 2; j <= MAX_SIZE; j += i) {
      hit[j] += cnt[i];
    }
  }
 
  for (let i = 1; i < input.length; i += 1) {
    ans += hit[input[i]] + "\n";
  }
  return ans;
};
 
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(Number);
console.log(solution(input));

복잡도

시간: O(M log M) — M은 최대 번호
공간: O(M)

문제