P.27172 수 나누기 게임

코드

package Baekjoon.Class;

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

public class P_27172 {

    static int max = 0;
    static int n;
    static int[] arr;
    static boolean[] nums = new boolean[1000001];
    static int[] score;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        for (int i = 0; i < n; i++) {
            max = Math.max(max, arr[i]);
            nums[arr[i]] = true;
        }

        score = new int[max + 1];
        sieve();

        for (int i : arr) {
            bw.write(score[i] + " ");
        }

        bw.flush();

        bw.close();
        br.close();
    }

    private static void sieve() {
        for (int i = 0; i < n; i++) {
            for (int j = 2 * arr[i]; j <= max; j += arr[i]) {
                if (nums[j]) {
                    score[j]--;
                    score[arr[i]]++;
                }
            }
        }
    }
}

코드 설명

에라토스테네스의 체를 응용하는 방법으로 해결했다.일반적인 에라토스테네스의 체는 다음과 같다.

boolean[] sieve = new boolean[max + 1];
    Arrays.fill(sieve, true);
    for (int i = 2; i * i <= max; i++) {
        if (sieve[i]) {
            for (int j = i; j <= max; j += i) sieve[j] = false;
        }
    }
}

소수와 합성수를 판별하는 알고리즘인데 약수를 찾는 코드로 바꾸어 봤다.

달라진 점은 i가 입력 받은 배열의 원소만 참조한다는 것이다.

브루트포스 + 에라토스테네스의 체로 보면 이해가 쉬울 것 같다.

 

문제는 시간이었다.

처음에는 약수를 ArrayList에 저장하여 main에서 이 약수가 입력받은 arr에 존재하는지 확인하는 작업을 했다.

이 때 다시 약수 리스트 혹은 입력 받은 리스트를 순회해야하므로 sieve() 함수에서 약수를 구하려고 브루트포스를 한 것이 의미가 없는 행동이 되어버린다.

 

따라서 score 계산을 sieve()함수에서 곧바로 해주는 방식을 택했다.

이 방식의 경우 대상 넘버(j)와 약수(i)가 arr에 존재하는지 확인을 해주는 작업이 필요하다. 

무턱대고 score를 변경해버리면 입력 받은 배열 내에서의 score가 아닌 1부터 MAX까지의 배열에서의 score가 구해지게 된다.

이 작업은 결국 입력 받은 배열의 순회를 초래하는데 이럴 경우 n * MAX / 2 * n이 되면서 시간초과가 발생한다.

이를 해결하기 위해 문제에서 주어진 최대 정수 크기인 1,000,000를 포용할 수 있는 boolean 배열을 두고 입력받은 배열의 원소의 경우 true로 바꾸어 sieve() 함수에서 O(1) 참조가 가능하게 해 주었다.