강의로 돌아가기
송동훈

7, 8, 9 런타임 오류

테스트 1 〉 통과 (1.51ms, 45MB)
테스트 2 〉 통과 (1.46ms, 48.4MB)
테스트 3 〉 통과 (1.76ms, 44.9MB)
테스트 4 〉 통과 (5.96ms, 48.6MB)
테스트 5 〉 통과 (18.44ms, 49.2MB)
테스트 6 〉 통과 (103.55ms, 56.9MB)
테스트 7 〉 실패 (런타임 에러)
테스트 8 〉 실패 (런타임 에러)
테스트 9 〉 실패 (런타임 에러)

1~6번은 모두 통과하고 7, 8, 9에서 오류가 발생합니다.
정확히는 회귀부분에서 오류가 발생하는데 메모리 문제일까요?
ArrayList 를 primitive로 바꾼다고 크게 향상되지는 않을거 같습니다.

코드상의 논리적인 문제일까요 아니면 성능상의 문제일까요? 오류코드나 디버그를 할 수 없으니 잘 모르겠네요 ㅠㅠ

작성중인 코드―Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.ArrayList;

class Solution {
    class Vertex{
        int number;
        ArrayList<Vertex> edge;

        Vertex(int number){
            this.number = number;
            this.edge = new ArrayList<Vertex>();
        }
        public int getNumber(){return this.number;}
        public ArrayList<Vertex> getEdges(){return this.edge;}
        public void addEdge(Vertex vertex){this.edge.add(vertex);}
    }

    // global var.
    public int[] checkedList;
    public int[] depthTable;

    public int solution(int n, int[][] edge) {
        Vertex[] vl = new Vertex[n];    // for Vertex
        int answer = 0, max=0;  // for max. depth
        // init. table
        checkedList = new int[n];
        depthTable = new int[n];

        // init. edge
        for(int[] link : edge){
            // sync. index
            int n1 = link[0]-1;
            int n2 = link[1]-1;
            // set edge
            if(vl[n1] == null) vl[n1] = new Vertex(link[0]);
            if(vl[n2] == null) vl[n2] = new Vertex(link[1]);
            vl[n1].addEdge(vl[n2]);
            vl[n2].addEdge(vl[n1]);
        }

        // set depth table
        this.setDepthTableFrom(vl[0], 1);

        // count max. depth Vertex
        for(int depth : depthTable){
            if(depth==max) answer++;
            else if(max<depth){
                max = depth;
                answer=1;
            }
        }

        return answer;
    }

    public void setDepthTableFrom(Vertex v1, int depth){
        checkedList[v1.getNumber()-1]=1;    // set checked

        for(Vertex linkedVertex : v1.getEdges()){
            int lvIndex = linkedVertex.getNumber()-1;

            // excepting case
            if(checkedList[lvIndex] != 0    // cycle
               || (depthTable[lvIndex] != 0 && depthTable[lvIndex] <= depth)   // No need to update
              ) continue;

            // update depthTable
            checkedList[lvIndex] = 1;
            depthTable[lvIndex] = depth;
            setDepthTableFrom(linkedVertex, depth+1);  // recursive check
            checkedList[lvIndex] = 0;
        }
    }
}
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.