[BOJ] 27172. 수 나누기 게임 (🥇, 정수론, 소수)

🔗

풀이

플레이어의 수는 최대 10만이기 때문에 모든 플레이어와 매칭하게 되면 10만 x 10만으로 시간초과가 발생할 수 있다.

모든 플레이어에 대해 자신의 배수 점수를 가진 플레이어의 점수를 -1하고 본인의 점수는 +1하면 된다. 점수에 중복은 없으므로 10만개의 플레이어에 대해서 모두 배수를 구하고 배수가 현재 플레이어들 가운데 존재하면 해당 플레이어 점수를 감소하고 본인의 점수를 +1한다.

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

public 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[] cards = new int[N];
        Map<Integer, Integer> score = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
            score.put(cards[i], 0);
        }

        for (int i = 0; i < N; i++) {
            int x = cards[i];
            for (int j = 2 * x; j < 1_000_001; j += x) {
                if (score.containsKey(j)) {
                    score.put(j, score.get(j) - 1);
                    score.put(x, score.get(x) + 1);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            System.out.print(score.get(cards[i]) + " ");
        }
    }
}