글 읽기 - 자바 메모리초과 질문입니다.

alalssg 5년 전 0

처음 문제를 풀었을때는 시간초과가 발생했습니다.

for(int i=2; i < size-1; i++){

int dist1 = arr[i] - arr[i-1];

int dist2 = arr[i+1] - arr[i];
}

두 거리의 최대 공약수를 구하면서 그동안 구해진 제일 작은 최대공약수를 모든 수의 공약수로 보고 이 수의 공약수를 구하는 방식으로 문제를 풀었습니다.

이렇게 하니 시간초과가 발생하였고 고민을 하던중 힌트를 얻어 아래와 같이 작성하였습니다.

기존 최대공약수와 다음 간격의 값으로 새로운 최대공약수를 구하는 방식으로 최대공약수를 구했습니다.

하지만 이번에는 메모리가 초과 됐다는 에러가 나옵니다.
물론 다른 분들이 자바로 풀이한 소스도 있지만 그래도 제가 생각한 방법이 왜 안되는지 먼저 알고 싶어서 질문을 올립니다.

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int size = Integer.parseInt(br.readLine());
		
		int[] arr = new int[size];
		
		for(int i=0; i < size; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(arr);
		
		int gcd = arr[1] - arr[0];
		
		for(int i=2; i < size; i++) {
			int dist1 = arr[i] - arr[i-1];
			
			gcd = getGCD(gcd, dist1);
		}
		
		dividers(gcd);
	}

	public static int getGCD(int a, int b) {
		if(b == 0) return 0;
		
		while(b > 0) {
			int tmp = a;
			a = b;
			b = tmp%b;
		}
		return a;
	}
	
	private static void dividers(int num){
		boolean[] dividers = new boolean[num+1];
		dividers[num] = true;
		for(int i = 1; i <= Math.sqrt(num); i++){
			if(num % i ==0){
				dividers[i] = true;
				dividers[num / i] = true;
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int i=2; i <= num; i++) {
			if(dividers[i]) sb.append(i + " ");
		}
		System.out.println(sb.toString());
	}
}

startlink 5년 전 1

dividers(num) 에서 num이 매우 클 수 있습니다.

종이에 적은 수가 1,000,000,000 이기 때문에, 서로소인 1억 이상의 자연수 2개를 입력으로 넣으면, 엄청난 메모리를 사용할 것 같습니다.

alalssg 5년 전 0

답변 정말 감사합니다!

어떤게 문제인가 고민을 하다가 결국엔 boolean[] dividers = new boolean[num+1]; 이게 문제였습니다.

약수가 절대 num 만큼 존재 하지 않는데 불필요한 메모리를 사용한거 같습니다.

정말 감사합니다!!

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

문제

문제

출처

ICPC

자바 메모리초과 질문입니다.

alalssg 5년 전 0

startlink 5년 전 1

alalssg 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말