문제

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

《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다.

《수 나누기 게임》의 규칙은 다음과 같습니다.

게임을 시작하기 전 각 플레이어는
$1$부터
$1\,000\,000$ 사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다.
매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다.
결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지가
$0$이면 승리합니다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어 떨어지면 패배합니다. 둘 다 아니라면 무승부입니다.
승리한 플레이어는
$1$점을 획득하고, 패배한 플레이어는
$1$점을 잃습니다. 무승부인 경우 점수의 변화가 없습니다.
본인을 제외한 다른 모든 플레이어와 정확히 한 번씩 결투를 하고 나면 게임이 종료됩니다.
《수 나누기 게임》의 결과를 가지고 한별이와 내기를 하던 은하는 게임이 종료되기 전에 모든 플레이어의 점수를 미리 알 수 있을지 궁금해졌습니다. 은하를 위해 각 플레이어가 가지고 있는 카드에 적힌 수가 주어졌을 때, 게임이 종료된 후의 모든 플레이어의 점수를 구해주세요.

입력
첫 번째 줄에 플레이어의 수
$N$이 주어집니다.

두 번째 줄에 첫 번째 플레이어부터
$N$번째 플레이어까지 각 플레이어가 가지고 있는 카드에 적힌 정수
$x_{1}$,
$\cdots$,
$x_{N}$이 공백으로 구분되어 주어집니다.

출력
첫 번째 플레이어부터
$N$번째 플레이어까지 게임이 종료됐을 때의 각 플레이어의 점수를 공백으로 구분하여 출력해주세요.

제한

$2 \le N \le 100\,000$ 
모든
$1 \le i \le N$에 대해
$1 \le x_i \le 1\,000\,000$입니다.
모든
$1 \le i < j \le N$에 대해
$x_i \ne x_j$입니다. 즉, 어떤 수도
$x$에서 두 번 이상 등장하지 않습니다.

예제 입력 1
3
3 4 12
예제 출력 1
1 1 -2

예제 입력 2
4
7 23 8 6
예제 출력 2
0 0 0 0

접근

소수 판정 문제라는 건 읽자마자 느낌이 왔지만 나에게 에라토스테네스의 체는 볼 때마다 새로운 것이라... 어떻게 하는지 전혀 머릿속에 남아 있지 않았다.
그래서 그냥 당연히 시간 초과가 날 걸 알면서도... 처음에는 그냥 무식한 접근을 해봤다.
각 카드의 순서 정보인 인덱스 값을 Map에 저장한 다음 정렬을 했다. 그리고 각 카드를 순회하면서 자신의 배수인 숫자들을 하나씩 셌다. 정렬되어 있으니 자신의 2배보다 작은 수가 나오기 전까지 가장 큰 수부터 하나씩 확인하며 세어 나가는 식...
그러고 나서는 더 이상 내가 할 수 있는 게 없을 것 같아 풀이를 봤다.

구현

1차 시도 (시간 초과)

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Map<Integer, Integer> cards = new HashMap<>();
        int[] scores = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards.put(Integer.valueOf(st.nextToken()), i);
        }
        List<Integer> sorted = new ArrayList<>(cards.keySet());
        Collections.sort(sorted);
        for (int i = 0; i < N; i++) {
            for (int j = N - 1; (sorted.get(i) << 1) <= sorted.get(j); j--) {
                if (sorted.get(j) % sorted.get(i) == 0) {
                    scores[cards.get(sorted.get(i))]++;
                    scores[cards.get(sorted.get(j))]--;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int score : scores) {
            sb.append(score).append(" ");
        }
        System.out.println(sb.toString());
    }
}

시간 복잡도를 분석해보자.

우선 정렬을 수행하는데, 이는 O(NlogN)이다.
사실 정렬보다는 가장 중요한 병목 구간인 이중 for문을 봐야 한다.

for (int i = 0; i < N; i++) {  
    for (int j = N - 1; (sorted.get(i) << 1) <= sorted.get(j); j--) {  
        if (sorted.get(j) % sorted.get(i) == 0) {  
            scores[cards.get(sorted.get(i))]++;  
            scores[cards.get(sorted.get(j))]--;  
        }  
    }  
}

첫 번째 루프는 i번 반복되므로 O(N)이다.
두 번째 루프는 크기가 N인 리스트의 sorted의 끝에서부터 시작하여 (sorted.get(i) << 1) <= sorted.get(j)를 만족하는 동안 j를 감소시키며 반복한다. 따라서 두 번째 루프는 j가 0이 될 때까지 수행되지 않을 수도 있지만, 최악의 경우 O(N)이 될 가능성도 존재한다.
=> 즉, 최악의 경우 내가 구현한 코드의 시간 복잡도는 O(N^2) 이 된다. 그리고 N이 커## 질수록 시간 복잡도가 기하급수적으로 커지는 문제가 있다.

정답 풀이

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];
        boolean[] exists = new boolean[1000001];
        int[] score = new int[1000001];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
            // 입력에 존재하는 숫자에 대해 exists 배열에 true로 마킹
            exists[cards[i]] = true;
        }
		
        // 모든 카드를 순회하며 반복
        for (int i : cards) {
        	// 현재 카드의 모든 배수들을 확인
            for (int j = i * 2; j < 1000001; j += i) {
            	// i의 배수인 j가 입력에 존재했다면 i의 승점 증가, j의 승점 감소
                if (exists[j]) {
                    score[i]++;
                    score[j]--;
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int num : cards) {
            sb.append(score[num]).append(" ");
        }
        
        System.out.println(sb.toString());
    }
}

위와 같이 에라토스테네스의 체를 이용해 소수 판정하는 방식을 응용해 문제를 해결할 수 있었다.

시간 복잡도를 분석해보자.

for (int i : cards) {
    for (int j = i * 2; j < 1000001; j += i) {
        if (exists[j]) {
            score[i]++;
            score[j]--;
        }
    }
}

첫 번째 루프는 N회 반복되므로 O(N)이다.
두 번째 루프는 i의 배수만을 순회하며 1000001 미만까지 반복하기에 약 O(NlogM)번 수행된다. 내가 구현한 코드는 입력 값인 N에 따라 시간 복잡도가 크게 달라지지만, 이렇게 구현하면 N의 값이 아무리 커져도 시간 복잡도가 O(NlogN)을 벗어나지 않는다.

Appendix - 에라토스테네스의 체

다음은 에라토스테네스의 체를 이용해 1 이상 1000 이하의 정수에 대해 소수를 판별하는 알고리즘이다.

import java.util.*;

public class SieveOfEratosthenes {
    public static void main(String[] args) {
        int N = 1000;
        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
}

사실 별 거 아닌데,,, N의 제곱근까지 수행해야 한다는 게 아직도 잘 안 와닿고 헷갈린다.