글 읽기 - [Java] 시간 초과 문제

ineedwildturkey101 2년 전 0

실행시켰을 때는 케이스를 여러 개 해도 출력이 빠르게 나오는데 왜 제출에서는 시간 초과가 뜨는지 잘 모르겠습니다. 어느 부분이 잘못된 걸까요?

import java.io.*; // io 라이브러리 호출 - BufferedReader 사용
import java.util.*; // util 라이브러리 호출 - ArrayList 사용

class Main{
    public static void main(String[] args) throws IOException{ // BufferedReader의 예외 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedReader 호출

        int t = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수 입력
        for(int i = 0; i < t; i++){ // 테스트 케이스의 갯수만큼 반복
            int n = Integer.parseInt(br.readLine()); // 골드바흐 추측을 확인할 값 입력
            int[] pn = filter(n); // n보다 작은 소수 값을 저장한 배열 초기화
            int[] goldbach = {0, 10000}; // 골드바흐 파티션을 저장할 배열 초기화

            for(int a = 0; a < pn.length; a++){ // 골드바흐 파티션을 구성할 값을 구함
                for(int b = 0; b < pn.length; b++){
                    if(pn[a] >= pn[b] & n - pn[a] == pn[b] & goldbach[1] - goldbach[0] > pn[a] - pn[b]){
                        goldbach[1] = pn[a];
                        goldbach[0] = pn[b];
                    }
                }
            }
            
            System.out.println(goldbach[0] + " " + goldbach[1]); // 결과 출력
        }
    }

    static int[] filter(int input){ // 에라토스테네스의 체를 이용하여 n보다 작은 소수를 구하는 메소드
        ArrayList<Integer> temp1 = new ArrayList<Integer>(); // n의 제곱근보다 작은 소수 값을 저장할 동적 배열 초기화
        for(int i = 2; input >= Math.pow(i, 2); i++){
            switch(isPn(i)){
                case 0: temp1.add(i);
                default:
            }
        } // n의 제곱근보다 작은 값들의 소수 여부를 판단하여 배열에 저장
        int[] filterPn = new int[temp1.size()]; // n의 제곱근보다 작은 소수 값을 저장할 배열 생성
        for(int a = 0; a < temp1.size(); a++){
            filterPn[a] = temp1.get(a);
        } // 에라토스테네스의 체로 이용할 소수 값을 배열에 저장

        ArrayList<Integer> temp2 = new ArrayList<Integer>(); // n보다 작은 소수를 선별하여 저장할 동적 배열 초기화
        for(int j = 2; j < input; j++){ 
            switch(isPn(j, filterPn)){
                case 0: temp2.add(j);
                default:
            }
        } // n보다 작은 값들의 소수 여부를 판별하여 배열에 추가

        int[] pn = new int[temp2.size()]; // 반환을 위한 배열 생성
        for(int b = 0; b < temp2.size(); b++){
            pn[b] = temp2.get(b);
        }

        return pn; // 결과 값 반환
    }

    static int isPn(int num){ // 소수 여부를 판단할 메소드
        int isPn = 0;
        for(int x = 2; x < num; x++){
            if(num % x == 0) isPn = 1;
        }
        return isPn; // 소수 여부 판단 값 반환
    }
    static int isPn(int num, int[] pn){
        int isPn = 0;
        for(int x = 0; x < pn.length; x++){
            if(num % pn[x] == 0) isPn = 1;
        }
        return isPn; // 소수 여부 판단 값 반환
    }
}

fccva 2년 전 1

테스트 케이스마다 에라토스테네스 체를 새로 만들 필요가 없습니다.

그리고 보통 에라토스테네스의 체는 "루트 n 이하의 소수를 모두 저장해놨다가 하나씩 나눠보는 방식"이 아니라

"n이하의 모든 값에 대해서 소수인지 아닌지 미리 저장해두는 방식"입니다.

아래처럼 구현해두면 k가 소수인지 아닌지 isPrime[k]로 알 수 있습니다.

public static boolean[] eratosthenes() {
    boolean[] isPrime = new boolean[10_001];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i*i <= isPrime.length; i++) {
        for (int j = i+i; j < isPrime.length; j += i) {
            isPrime[j] = false;
        }
    }
    return isPrime;
}

ineedwildturkey101 2년 전 0

fccva님 답변 감사합니다.

에라토스테네스의 체를 그저 원리만 이해하고 접근하다 보니 복잡한 코드가 된 것 같네요.

배열이나 배열에 대한 메소드도 새롭게 알게 되었습니다.

fccva님의 메소드를 활용하여 BufferedReader와 BufferedWriter도 써가며 풀어봤는데 아직 시간 초과가 뜨네요. 골드바흐 파티션을 구하는 부분에 대해서 시간이 오래 걸리는 문제가 발생하는 것 같은데 조건이 길면 실행 시간에도 큰 영향이 있는 건가요?

골드바흐 파티션을 구하는 코드는 fccva님이 작성하신 메소드를 기반으로 다음과 같이 작성하였습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedReader 호출

int n = Integer.parseInt(br.readLine()); // 골드바흐 추측을 실행할 값 입력
int[] goldbach = {0, 10000}; // 골드바흐 파티션을 저장할 배열 생성

for(int a = 0; a < isPrime.length; a++){ // 골드바흐 파티션 중 큰 값 확인
    for(int b = 0; b < isPrime.length; b++){ // 골드바흐 파티션 중 작은 값 확인
        if(isPrime[a] == true & isPrime[b] == true & a + b == n & a >= b & goldbach[1] - goldbach[0] > a - b){
            goldbach[1] = a;
            goldbach[0] = b;
        } // 두 수가 골드바흐 추측을 성립시키며 차이가 가장 작으면 골드바흐 파티션으로 선정
    }
}

fccva 2년 전 1

이중루프를 돌 필요가 없습니다.

for문 하나로 확인할 수 있는 방법이 있습니다.

ineedwildturkey101 2년 전 0

확인과 힌트 감사합니다.

for문 한 개로 파티션을 구했더니 확실히 처리가 빨라진 것 같습니다.

덕분에 이것저것 많이 배우게 되었네요. 감사합니다!

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

문제

문제

출처

ICPC

[Java] 시간 초과 문제

ineedwildturkey101 2년 전 0

fccva 2년 전 1

ineedwildturkey101 2년 전 0

fccva 2년 전 1

ineedwildturkey101 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말