May LeetCoding Challenge[Day10] - Find the Town Judge

In a town, there are N people labelled 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 trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.
If the town judge exists and can be identified, return the label of the town judge. 

Otherwise, return -1.

Input: N = 4,
trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]

Output: 3

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제는 마을 판사가 누구인가 알아내는 문제이다.

 - 문제에는 조건이 3개 주어진다.

    1. 마을 판사는 아무도 믿지 않습니다.

    2. 모든 사람은 마을 판사를 신뢰합니다.

    3. 마을 판사는 오직 1명이고, 1과 2를 만족합니다.

 - input으로는 trust라는 배열이 주어진다. 배열에는 N번째 사람이 M번째 사람을 신뢰한다는 내용이 들어있다.

 - 해당 문제를 풀기위해서 생각한 방법은 "모든 사람은 마을 판사를 신뢰합니다."를 해결하기 위해서 카운팅을 한다.

 - "모든 사람은 마을 판사를 신뢰합니다.", 카운팅의 결과가 N-1 이라면, 해당 사람이 누구를 지목했는 지 확인하는 pointer배열을 확인해줘서, 만약 그 사람이 누구를 가리키고 있다면 판사가 아니고, 그 사람이 가리키고 있다면 판사가 되도록 했다.

 - counting과 pointer는 배열로 만들었지만, 맵 역할을 하고 있다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 더 간결하게 처리할 수 없었을까?

 

3. 내가 작성한 알고리즘

 

class Solution {
    public int findJudge(int N, int[][] trust) {
        if(trust.length == 0){
            return N;
        }
        
        int[] counting = new int[N+1];
        int[] pointer = new int[N+1];
        int maxPosition = 0;
        int max = 0;
        for(int i=0; i<trust.length ; i++){
            pointer[trust[i][0]] = trust[i][1];
            counting[trust[i][1]] = counting[trust[i][1]] + 1;
            if(max < counting[trust[i][1]]){
                max = counting[trust[i][1]];
                maxPosition = trust[i][1];
            }
        }
                                  
        if(counting[maxPosition] == N-1){
            if(pointer[maxPosition] != 0){
                return -1;
            }else{
                return maxPosition;
            }
        }
        
        return -1;   
    }
}

 

4. 내가 작성한 알고리즘 결과

 

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3286/

Explore - LeetCode