문제

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

나의 풀이

1. 해당 수까지의 소수를 prime 배열에 저장
2. 배열의 가장 큰 수부터 구하려는 수에서 빼서 소수의 합으로 M이 구해지는 지 판별 

시간복잡도
N * M-5 * M-2 최대!  <- 소수인지 판별하는 for문
M = 8, 3*3*6=54

첫번째 풀이

public class Prac {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            int M = Integer.parseInt(br.readLine());
            ArrayList<Integer> prime = new ArrayList<>();
			
            // 소수인지 판별하는 for문 , M = 16 경우 3-13까지 검사
            for (int j = 2; j < M-2; j++) {
                boolean isPrime = true;
                for (int k = 2; k < j; k++) {
                    if (j % k == 0) {
                      isPrime = false;
                      break;
                    }
                }
                if (isPrime) {
                    prime.add(j);				// [3, 5, 7, 11]
                }
            }

            int[] arr = new int[]{0, M};		// 정답을 넣을 배열	

            for (int j = prime.size()-1; j > -1; j--) {
                int re = M - prime.get(j);
                if (prime.contains(re) && prime.get(j) < arr[1] && prime.get(j)>= M/2) {
                    arr[0] = re;
                    arr[1] = prime.get(j);
                }
            }

            System.out.println(arr[0] + " " + arr[1]);

        }
    }
}

• 시간초과가 떠서 소수 판별하는 부분을 에라토스테네스의 체를 활용하는 방식으로 바꿔보기로 했다.

두번째 풀이

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());

        for (int i = 0; i < N; i++) {
            int M = Integer.parseInt(br.readLine());
            ArrayList<Integer> primes = new ArrayList<>();

            primes.add(1);
            primes.add(1);

            for (int j = 2; j < M-1; j++) {
                primes.add(0);
            }

            int sqrt = (int) Math.sqrt(M);

            for (int j = 2; j < sqrt + 1; j++) {
                if (primes.get(j) == 0) {                    // 0 이라면
                    for (int k = j+j; k < M-1; k += j) {     // i=2일 때, 4, 6, 8, 10 번째 리스트 값을 0 -> 1로 변경
                        primes.set(k, 1);                    // i=3,  9
                    }
                }
            }

            ArrayList<Integer> prime = new ArrayList<>();

            for (int j = 2; j < primes.size(); j++) {
                if (primes.get(j) == 0) {
                    prime.add(j);
                }
            }

            int[] arr = new int[]{0, M};

            for (int j = prime.size()-1; j >= 0; j--) {
                int re = M - prime.get(j);
                if (prime.contains(re) && prime.get(j) < arr[1] && prime.get(j) >= M/2) {
                    arr[0] = re;
                    arr[1] = prime.get(j);
                }
            }

            System.out.println(arr[0] + " " + arr[1]);

        }
    }
}

• 수가 커졌을 경우 뒤에서부터 하나씩 줄여나가는 방식이 시간이 많이 소요될 것 같았다.
• 테스트 케이스 4가 반례였다.
• 답은 맞았다고 했지만 간신히 통과한 수준이다.

참고 풀이

public class Prac {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        boolean[] prime = new boolean[10001];

        for (int i = 2; i <= Math.sqrt(10000); i++) {           // 해당 범위까지 소수 판별, true는 소수가 아님
            for (int j = i+i; j < 10000; j += i) {
                prime[j] = true;
            }
        }

        while (N-- > 0) {
            int M = Integer.parseInt(br.readLine());
            int x = M/2;                                       // 절반값을 정하고
            int y = M/2;

            int i = 0;      
            while (x - i > 1) {                                // 하나씩 빼고 더한 수가 소수인지 판별
                if (!prime[x - i] && !prime[y + i]) {
                    System.out.println((x-i) + " " + (y+i));
                    break;
                }
                i++;
            }
        }

    }
}

• 에라토스테네스의 체 방식을 활용해 범위까지의 수를 모두 소수 판별을 끝내놓는다.
• 소수 차이의 차가 작은 값을 도출해내야 하므로 반값에서 시작하여 하나씩 더하고 뺀 수가 소수이면 출력

나의 풀이와 비교했을 때 이중for문을 사용하지 않았다. 

9020번 에토 체 풀이