## FAMILYTREE 계속해서 메모리 초과가 뜨네요...

• clearpal6

이 코드는 알고리즘 해결전략 책에있는 C++코드를 자바코드로 바꿔서 나온 코드입니다.(RMQ 알고리즘이용)
책에 나온거 참고해서 한건데 자꾸 RTE(메모리초과)가 나오는데 어디서 잘못된걸까요????? 도와주시면 감사하겠습니다.

public class Main {

final static int MAX_N=100000;
private static int N;
private static int M;
private static int nextSerial;
private static int noToserial[]=new int[100000];
private static int serialTono[]=new int[100000];
private static int loclnTrip[]=new int[100000];
private static int depth[]=new int[100000];
static ArrayList<Integer> child[]=new ArrayList[100000];

public static void main(String[] args) {
// TODO Auto-generated method stub
try{
BufferedWriter writer=new BufferedWriter(new OutputStreamWriter(System.out));

while(Cases-->0){
for(int i=0;i<MAX_N;i++){
child[i]=new ArrayList<Integer>();
}
N=Integer.parseInt(input[0]);
M=Integer.parseInt(input[1]);

int parent;
for(int i=1;i<N;i++){
parent=Integer.parseInt(input[i-1]);
}
RMQ rmq=prepareRMQ();
int a,b;
for(int i=0;i<M;i++){
a=Integer.parseInt(input[0]);
b=Integer.parseInt(input[1]);
writer.append(String.valueOf(distance(rmq,a,b)));
writer.append("\n");
}

}
writer.flush();
writer.close();
}catch(Exception e){
e.printStackTrace();
}
}
private static int distance(RMQ rmq,int u, int v) {
// TODO Auto-generated method stub
int lu=loclnTrip[u];
int lv=loclnTrip[v];
if(lu>lv){
int temp=lu;
lu=lv;
lv=temp;
}
int lca=serialTono[rmq.query(lu,lv)];
return depth[u]+depth[v]-2*depth[lca];
}
private static RMQ prepareRMQ(){
nextSerial=0;
ArrayList<Integer> trip = new ArrayList<Integer>();
traverse(0,0,trip);
return new RMQ(trip);
}
private static void traverse(int here, int d, ArrayList<Integer> trip) {
// TODO Auto-generated method stub
noToserial[here]=nextSerial;
serialTono[nextSerial]=here;
++nextSerial;

depth[here]=d;

loclnTrip[here]=trip.size();

for(int i=0;i<child[here].size();i++){
traverse(child[here].get(i),d+1,trip);
}

}

}
class RMQ{
int n;

int []rangeSize;
RMQ(int []array){
n=array.length;
rangeSize=new int[n*4];
init(array,1,0,n-1);
}
RMQ(ArrayList<Integer> array){
n=array.size();
rangeSize=new int[n*4];
init(array,1,0,n-1);
}
private int init(ArrayList<Integer> array, int node, int left,int right) {
// TODO Auto-generated method stub
if(left==right)
return rangeSize[node]=array.get(left);

int mid=(left+right)/2;
int leftMin=init(array,node*2,left,mid);
int rightMin=init(array,node*2+1,mid+1,right);
return Math.min(leftMin,rightMin);
}
private int init(int[] array, int node, int left, int right) {
// TODO Auto-generated method stub
if(left==right)
return rangeSize[node]=array[left];

int mid=(left+right)/2;
int leftMin=init(array,node*2,left,mid);
int rightMin=init(array,node*2+1,mid+1,right);
return Math.min(leftMin,rightMin);
}
int query(int left,int right){
return query(left,right,1,0,n-1);
}
private int query(int left, int right, int node, int leftNode, int rightNode) {
// TODO Auto-generated method stub
if(right<leftNode || left>rightNode)
return 1000000;

if(leftNode>=left && rightNode<=right)
return rangeSize[node];

int mid=(leftNode+rightNode)/2;
return Math.min(query(left,right,node*2,leftNode,mid),
query(left,right,node*2+1,mid+1,rightNode));
}

}

4년 전
##### 2개의 댓글이 있습니다.

• JongMan

자바 메모리 사용량이 많아서 그런 것 같습니다. 해당 문제 메모리 제한을 256mb로 늘렸으니 다시 시도해 보세요. 재채점해보니 정상적으로 채점되네요.

4년 전

• clearpal6

감사합니다^^

4년 전
• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.