[Leetcode 14/100] Find the Town Judge - Easy

문제 풀이 방식

LinkedList로 Graph를 구현하여 풀이

주의할 점

엣지 케이스를 주의 할 것, 시간 복잡도를 신경 쓸 것

그래프 문제를 많이 경험해보지 못해서 순수 구현으로 푼 느낌이다.

다른 discuss를 보고 풀이를 참고해서 다시 풀어봐야 할 것 같음..

소스코드

class Solution {
    LinkedList<LinkedList> res = new LinkedList();
    int sizeFlag = 0;
    public int findJudge(int N, int[][] trust) {
        if(N == 1) return 1;
        makeGraph(N, trust);
        LinkedList judgeList = findByJundgeList();
        if(sizeFlag > 1) return -1;
        return findByJudge(judgeList);
    }
    
    public int findByJudge(LinkedList<Integer> judgeList){
        
        for(int i=0; i<judgeList.size(); i++){
            int judgeNum = judgeList.get(i);
            int flag = 0;
            for(int j=0; j<res.size(); j++){
                if(res.get(j).size() == 0) continue;
                LinkedList list = res.get(j);
                for(int k=0; k<list.size(); k++){
                    // System.out.println("judgeNum " + judgeNum + " listNum " + list.get(k));
                    if((int)list.get(k) == judgeNum){
                        flag = 1;
                    }
                }
                if(flag == 1){
                    continue;
                } else {
                    break;
                }
            }
            if(flag == 1){
                return judgeNum;
            }
        }
        
        return -1;
        
    }
    
    public LinkedList<Integer> findByJundgeList(){
        
        LinkedList judgeList = new LinkedList();
        
        for(int i=0; i<res.size(); i++){
            if(res.get(i).size() == 0){
                judgeList.add(i+1);
                sizeFlag++;
            }
        }
        return judgeList;
    }
    
    public LinkedList<LinkedList> makeGraph(int N, int[][] trust){
        
        for(int i=0; i<N; i++){
            res.add(new LinkedList());
        }
        
        for(int i=0; i<trust.length; i++){
            LinkedList list = res.get(trust[i][0]-1);
            list.add(trust[i][1]);
        }
        
        return res;
    }
}