글 읽기 - 자바 메모리 관련 질문 드립니다.

qotjdgus96 2년 전 0

자바 메모리 관련 질문 드립니다.

기존 제출 코드를 보면 tree배열의 경우 N보다 큰 2의 제곱수이므로 최대 크기가 2048*2로 12(header)+4(length)+4096*4(reference type size) = 16,400 byte로 예상됩니다.

edge 배열은 M의 최대 크기가 N(N-1)/2인 1,999,000으로 12(header)+4(length)+1999000*4(reference type size) = 1,999,020 byte로 예상됩니다.

그러면 총 2,015,420 byte로 대략 2MB가 됩니다.

그런데 메모리초과가 뜨고 자바로 문제를 푼 사람은 없을 뿐더러 틀린 이유중 반수가 메모리 초과였습니다.

그래서 실험용코드로 입력을 받기만 하고 딱히 다른 변수 선언도 하지 않고 제출했습니다.

답을 0으로 반환할 뿐인데로 틀렸습니다가 아닌 9%에서 메모리 초과만 반복해서 뜹니다.

그래서 혹시 설정이 잘못되어 있진 않나 싶어 문의드립니다.

감사합니다.

// 기존 제출 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
    private static int PIV = 1;
    private static int[] tree;
    
    public static void update(int n, int v){
        n += PIV;
        tree[n] = v;
        n /= 2;
        while(n>0){
            tree[n] = tree[n*2] + tree[n*2+1];
            n /= 2;
        }
    }
    
    public static int query(int l, int r){
        l += PIV;
        r += PIV;
        int sum = 0;
        while(l<=r){
            if(l%2==1) sum += tree[l++];
            if(r%2==0) sum += tree[r--];
            l /= 2;
            r /= 2;
        }
        return sum;
    }
    
    public static void print(){
        int tmp = 1;
		for(int i=1; i<PIV*2; i++){
		    if(tmp==i){
		        System.out.println();
		        tmp <<= 1;
		    }
		    System.out.printf("%d ", tree[i]);
		}
		System.out.println();
    }
    
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		while(PIV<N) PIV <<= 1;
		tree = new int[PIV*2];
		int[] edge = new int[M];
		for(int i=0; i<M; i++){
		    st = new StringTokenizer(br.readLine());
		    int a = Integer.parseInt(st.nextToken());
		    int b = Integer.parseInt(st.nextToken());
		    edge[i] = a*10000+b;
		}
		
		Arrays.sort(edge);
		
		int ans = 0;
		for(int i=0; i<M; i++){
		    update(edge[i]%10000, tree[edge[i]%10000+PIV]+1);
		    ans += query(edge[i]%10000+1, PIV-1);
		}
		
		System.out.println(ans);
		br.close();
	}
}
////////////////////////////////////////////////////////////////////

// 실험용 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
        int ans = 0, a, b;
		for(int i=0; i<M; i++){
		    st = new StringTokenizer(br.readLine());
		    a = Integer.parseInt(st.nextToken());
		    b = Integer.parseInt(st.nextToken());
		}
        
		System.out.println(ans);
		br.close();
	}
}

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

문제

문제

출처

ICPC

자바 메모리 관련 질문 드립니다.

qotjdgus96 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말