글 읽기 - 자바 시간초과 나는 이유가 뭘까요

koorung 2년 전 0

값은 잘 나오는거 같은데 시간초과가 뜨네요 for문 중첩때문에 그런걸까요?

// 해결했습니다 돌아가는 코드였는데 이상한짓 했네요

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {

        // BufferedReader과 InputStreamReader로 입력값을 받고
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        // 1. 입력값 t만큼 반복함
        for (int i = 0; i < t; i++) {

            // 2. 반복되는 만큼 num을 입력하여
            int num = Integer.parseInt(br.readLine());
            makePrime(num);

            List<Integer> list = new ArrayList<>();
            // 3. num의 입력값으로 인해 만들어지는 prime 배열을 for문을 돌려
            for (int k = 0; k < prime.length; k++) {
                    // 4. 둘 다 소수인 경우에 입력값과 그 값이 일치할 경우 두 값을 출력
                    if (prime[k] == false && prime[num - k] == false) {
                       list.add(k);
                    }
            }
            int o = list.get(list.size() /2);
            System.out.println((num - o) + " " + o);
        }
    }

    // 에라토스테네스의 체를 이용하여 소수에 대한 boolean 배열을 만듦
    // (true = 소수가 아님, false = 소수)
    private static boolean[] prime;

    private static void makePrime(int n) {
        prime = new boolean[n + 1];

        // 2 이하의 경우 판별할 필요도 없으므로 스킵
        if (n < 2) {
            return;
        }

        // 0과 1은 소수가 아니므로
        prime[0] = prime[1] = true;

        // 2부터 n의 제곱근까지 for문을 돌림
        for (int i = 2; i < Math.sqrt(n); i++) {

            // 이미 검사한 숫자는 스킵함
            if (prime[i] == true) {
                continue;
            }

            // 각 n에 대한 배수는 소수가 아니므로 true
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

자바 시간초과 나는 이유가 뭘까요

koorung 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말