글 읽기 - 33%에서 멈추는데 어디서 시간 초과간 난거지 모르겠네요ㅜ

yjin99 1년 전 0

질문 올라온거 찾아보며 에라토스테네스의 체 반복문 범위도 i*i<=1000000으로 고치고

소수 쌍 찾는것도 수정했는데 시간 초과나는 원인을 못 찾겠습니다. 도움 부탁드려요.

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

public class Main {
    static boolean[] isPrime;
    static ArrayList<Integer> primes = new ArrayList<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        getPrime();
        int n;
        while (true) {
            n = Integer.parseInt(br.readLine());
            if (n == 0) break;


            int l = 0;
            int r = 0;
            for (int i = n - 1; i > 1; i--) {
                if (primes.contains(i)) {
                    r = primes.indexOf(i);
                    break;
                }
            }

            for (int i = r; i >= (r + 1) / 2; i--) {
                if (primes.contains(n - primes.get(i))) {
                    sb.append(n + " = " + (n - primes.get(i)) + " + " + primes.get(i)).append("\n");
                    break;
                }
            }

        }
        System.out.println(sb.toString());
    }

    public static void getPrime() {
        int size = 1000001;
        isPrime = new boolean[size];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= size - 1; i++) {
            if (!isPrime[i]) continue;

            for (int k = (i * 2); k < size; k += i) {
                isPrime[k] = false;
            }
        }
        for (int i = 2; i < size; i++) {
            if (isPrime[i]) primes.add(i);
        }
    }
}

aeternussm 1년 전 2

arrayList의 contains와 indexOf 시간복잡도가 O(n)이라 느릴것같아요

primes.contains(i) 를 isPrime[i]로 쓰면 더 빠를것같아요

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

문제

문제

출처

ICPC

33%에서 멈추는데 어디서 시간 초과간 난거지 모르겠네요ㅜ

yjin99 1년 전 0

aeternussm 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말