글 읽기 - [JAVA] 안녕하세요 시간초과 문제입니다

ehfkswl 5년 전 0

안녕하세요

답은 나오는거 같은데 자꾸 시간초과가 납니다

코드는 아래와 같고 에라토스테네스의 체를 구현하려고 하였습니다

먼저 max 길이의 2부터 자연수 배열을 만들고 2부터 각 수의 배수를 지어나가는 식으로 구현하였습니다

그리고 이 소수의 제곱이 max보다 커지게되면 배수를 따질 필요가 없으므로 while문을 빠져나오게 했습니다

시간을 더 줄여야할 부분은 자연수 배열을 만드는 for문이나 소수의 배수를 remove를 하는 방법을 고쳐야 하는것 같은데

정확히 어떤 부분이 잘못됐는지 모르겠네요

알려주시면 감사하겠습니다!

import java.util.*;
import java.io.*;

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

		Scanner sc = new Scanner(System.in);
		int min = sc.nextInt();
		int max = sc.nextInt();

		prime(min,max);
	}

	public static void prime(int min, int max){

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		List<Integer> list = new ArrayList<Integer>();
		int a = 0;
		int quo = 0;

		for(int i = 2; i<=max; i++){
			list.add(i);
		}

		while(true){
			quo = list.get(a);
			if(quo*quo>max){
				break;
			}
			for(int j = a+1; j<=list.size(); j++){
				if(j == list.size()){
					break;
				}
				if(list.get(j)%quo == 0){
					list.remove(j);
					j--;
				}
			}
			a++;
			}
		try{
			for(int i = 0; i<list.size(); i++){
				if(list.get(i) >= min){
					bw.write(String.valueOf(list.get(i)) + " ");
				}
			}
			bw.flush();
			bw.close();
		}	catch(IOException e){
			System.out.println("asd");
		}


	}
}

jh05013 5년 전 0

https://www.acmicpc.net/blog/v...
ArrayList의 중간에 뭔가를 끼워넣고 빼는 건 O(N)입니다.

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

문제

문제

출처

ICPC

[JAVA] 안녕하세요 시간초과 문제입니다

ehfkswl 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말