[Algo] 백준 27172 수 나누기 게임 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/27172

메모리 : 31816KB

시간 : 452ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int[] save = new int[N];
        boolean[] check = new boolean[1000001];
        int[] dp = new int[1000001];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int max = 0;
        for (int i = 0; i < N; i++) {
            save[i] = Integer.parseInt(st.nextToken());
            check[save[i]] = true; //수가 존재한다는 체크배열
            max = Math.max(max, save[i]); //최대값 구하기
        }
        for (int i = 0; i < N; i++) {
            //최대값까지 배수 구하기
            for (int j = save[i] * 2; j <= max; j += save[i]) {
                if (check[j]) {
                    dp[save[i]]++; //나누는 수는 더해주고
                    dp[j]--; //나눠진수는 빼주기
                }
            }
        }
        for (int i = 0; i < N; i++) {
            sb.append(dp[save[i]]).append(" ");
        }
        System.out.print(sb);
    }
}

죽은코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int[] save = new int[N];
        int[] arr = new int[N];
        int[] dp = new int[1000000];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            save[i] = Integer.parseInt(st.nextToken());
            arr[i] = save[i];
        }
        Arrays.sort(save);
        int max = save[N - 1];
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (save[j] % save[i] == 0) {
                    dp[save[i]]++;
                    dp[save[j]]--;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            sb.append(dp[arr[i]]).append(" ");
        }
        System.out.print(sb);
    }
}

풀이

8번이나 제출..
메모리가 큰 것을 확인한 후, 정렬을 해서 작은 수 부터 큰수를 나눠가며 dp에 체크하는 정렬그리디스러운 방법을 생각했으나.. 4%에서 바로 시간초과. sort가 시간초과의 주범인것 같아 정렬 버리고 다시 생각해보기.
입력을 받은 후 순서대로 배수를 만들어가며 n의 배수가 존재할때 = n++, 배수-- 로 카운트해준다.
뭔가 완탐같은 기분이 드는데.. sort보다 이게 더 빠르다니. 믿을 수 없