마을 판사 찾기

문제

마을에 1부터 N의 고유 번호를 가진 사람들이 있다. 소문으로는 마을 사람 중에 마을 판사가 있다고 한다. 마을 판사가 실제로 존재한다면,

• 마을 판사는 아무도 믿지 않는다.
• 다른 모든 사람들은 마을 판사를 믿는다.
• 마을 판사가 있다면 오직 한명 뿐이다.

2차원 배열 trust가 주어졌을 때, trust[i] = {a, b}는 고유 번호가 a인 사람이 고유 번호가 b인 사람을 믿는다는 것을 의미한다고 한다.

마을 판사가 존재한다면 마을 판사의 고유 번호를, 존재하지 않는다면 -1을 출력하는 프로그램을 작성하시오.

(단, a가 b를 믿고 b가 c를 믿는다고 할 때, a가 c를 믿는다는 의미는 아니다.)

입력설명

• 2 < N <= 10000
• 0 <= trust.length <= 10000

출력설명

마을 판사의 고유 번호를 정수로 반환

매개변수 형식

• N = 3
• trust = {{1, 3}, {2, 3}}

반환값 형식

3

 

 

 

풀이 방법

1부터 N까지 사람 중 trust 배열에서 a 집합에는 한번도 나오지 않고, b 집합에서는 판사번호만 (N-1)번 나와야한다.

 

import java.util.*;

class Solution {
    public int solution(int N, int[][] trust) {
        if (trust.length == 0) {
            return -1;
        }
        for (int i = 1; i <= N; i++) {
            int finalI = i;
            if (Arrays.stream(trust).noneMatch(x -> x[0] == finalI)
                    &&
                    Arrays.stream(trust).filter(x -> x[1] == finalI).count() == (N - 1)
            ) {
                return finalI;
            }
        }
        return -1;
    }
}