[코딩연습] Find the Town Judge 마을판사 찾기

LeetCode 문제 중 난이도 Easy인 Find the Town Judge이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

마을엔 1부터 N으로 표기되는 N명의 사람들이 있다. 이들 중 한사람이 비밀스러운 마을 판사라는 소문이 있다.

만약 마을판사가 존재한다면

1. 마을판사는 아무도 신뢰하지 않는다.

2. 모든사람들(마을판사를 제외한)은 마을판사를 신뢰한다.

3. 위의 1,2 조건을 만족하는 사람은 딱 한명 뿐이다.

입력으로 trust 배열이 주어진다. trust[i]=trust[a,b]는 a가 b를 신뢰한다는 의미이다.

마을판사가 존재한다면 그사람의 번호를 리턴하고 존재하지 않는다면 -1을 리턴하라.

* 1 ≤ N ≤ 1000

* trust.length ≤ 10000

* trust[i] are all different

* trust[i][0] != trust[i][1]

* 1 ≤ trust[i][0], trust[i][1] ≤ N

마을판사가 존재하고 x라고 하자. 모두가 x를 신뢰해야 하므로 ①trust배열 안에 [1,x],[2,x],[3,x]....[n,x]가 전부 있어야 하고 x는 아무도 신뢰하지 않으므로 ②[x,n]은 있으면 안된다.

이 값을 계산하기 위해 tsum[N] 배열을 만들어서 tsum[x-1]에 x를 믿는 사람들의 번호의 합을 저장한다. x가 마을판사이려면 자기자신인 x를 제외한 1~N의 사람들이 전부 x를 신뢰해야 하므로 tsum[x-1][1]은 1~N의 합-x 어야 한다. 그리고 x는 아무도 믿지 않으므로 [x,b]일 때 tsum[x-1]의 값에 -1을 집어넣는다.

이렇게 하면 x를 제외한 모두가 x를 믿는다고 해도 tsum[x-1]의 값은 1~N-x보다 작아진다. -1대신에 아무 음수 또는 N(N+1)/2보다 큰값을 집어넣어도 된다. 코드는 다음과 같다.

class Solution {
    public static int findJudge(int N, int[][] trust) {
        int[] tsum = new int[N];
        int nsum = N*(N+1)/2;
        
        //[a,b]이면 tsum[b-1]에 a를 더함
        for(int i=0 ; i<trust.length ; i++){
            tsum[trust[i][1]-1] = tsum[trust[i][1]-1] + trust[i][0];
            tsum[trust[i][0]-1] = -1;
        }
        
        //tsum[x-1]이 1~N의 합과 같으면 x 리턴
        for(int i=0 ; i<tsum.length ; i++){
            if(tsum[i]+i+1 == nsum){
                return i+1;
            }
        }
        
        //그런 값이 없으면 -1 리턴
        return -1;
    }
}
 

이 방법의 시간복잡도는 O(n) 공간복잡도도 O(n)이다.

문제 출처 - https://leetcode.com/problems/find-the-town-judge