leetcode -997. Find the Town Judge

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

 

Example 1:

Input: n = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

문제 : 판사는 몇번째 사람인지 찾는문제 (n 명이 주어지며, [[1,3],[2,3]] 이면 1>3번을 믿고, 2>3번을 믿으므로 3번이판사

1. 판사는 아무도 믿지않는다.

2. 모든사람이 판사를 믿는다. (한사람이 두명을 믿을수도 있음)

3. 1,2 번을 만족하는 사람은 오직 한사람이다.

 

풀이

vertext : 그래프에서, 해당번호의 사람을 몇명의 사람들이 믿는지를 저장할 배열

class Solution {
    public int findJudge(int n, int[][] trust) {
        
        int[] vertex = new int[n+1];
        
        for(int[] v : trust){
            vertex[ v[0] ]--;
            vertex[ v[1] ]++;
        }
        
        for(int i=1;i<vertex.length;i++){
            if(vertex[i] == n-1) return i;
        }
      
        return -1;
    }
}

 

Example 2: 의 경우 그래프

 

vertex 값은 최종적으로

[0, -1, -1, 2] 가 될것이다. 따라서 판사는 3번 이다. 

 

Example 3: 의 경우 그래프

vertex 값은 최종적으로

[0, 0, -1, 1] 가 될것이다. 따라서 판사는 존재하지 않음. -1 리턴