글 읽기 - java 메모리 초과 개선점 알려주세요ㅠㅠ

apso123 2년 전 0

메모리 초과 원인으로 의심 가는 부분은 그래프랑 스택(출력용) 부분입니다,,

그래프를 각각 K+1크기를 가진 ArrayList<Integer> N+1개를 붙여서 만들었는데 여기서 메모리 초과가 나는 걸까요?

혹시 인접 리스트를 이 방법 말고 구현 할 수 있는 더 좋은 방법이 있다면 부디 알려주세요

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

class Main{
    static boolean noInDeg[];
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> graph;
    static Stack<Integer> students = new Stack<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        String input[] = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        graph = new ArrayList<ArrayList<Integer>>(N+1);
        noInDeg = new boolean[N+1];
        visited = new boolean[N+1];

        Arrays.fill(noInDeg, true);

        for(int i=0; i<N+1; i++) {
            graph.add(new ArrayList<Integer>(K+1));
        }

        for(int i=0; i<K; i++){
            input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            graph.get(u).add(v);
            noInDeg[v]=false;
        }

        dfsAll();
    
        for(int i=0; i<N; i++){
            bw.write(students.pop()+" ");
        }
        bw.flush();
        bw.close();
    
    }

    static void dfsAll() {
        for(int u=1; u<graph.size(); u++){
            if(noInDeg[u])
                dfs(u);
        }
    }
    static void dfs(int u){
        for(int v: graph.get(u)){
            if(!visited[v]){
                dfs(v);
            }
        }
        students.add(u);
    }
}

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

문제

문제

출처

ICPC

java 메모리 초과 개선점 알려주세요ㅠㅠ

apso123 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말