[leecode] Find the Town Judge

https://leetcode.com/problems/find-the-town-judge/

문제해석

- 마을에 judge 는 단 한명. judge 는 아무도 믿지 않는다. judge 를 제외한 모든 사람은 judge 를 믿는다.

- 아래의 2가지 조건을 만족하면 judge 가된다.

     1. 믿는 사람이 아무도 없다.
     2. 나를 믿는 사람이 N-1 명이다. 

 

 그래프 만들기

사람들의 관계를 Graph 로 만들자.

for( const t of trust ) {
        
	const p1 = t[0]
	const p2 = t[1]

	// p1 은 p2 를 믿는다.
	trustYou[p1].push(p2) // 내가 믿는 사람들 
	trustMe[p2].push(p1) // 나를 믿는 사람들
}

Judge 를 찾기

for( let i=1; i<trustYou.length; i++) {
	// 믿는 사람이 없으며, 나를 믿는 사람이 N-1 명이면 judge 가 된다.
	if( trustYou[i].length === 0 && trustMe[i].length === N-1) {
		return i
	}
}

전체 코드

var findJudge = function(N, trust) {
    
    const trustYou = [...Array(N+1)].map(i=>new Array())
    const trustMe = [...Array(N+1)].map(i=>new Array())
    
    for( const t of trust ) {
        
        const p1 = t[0]
        const p2 = t[1]
        
        trustYou[p1].push(p2)
        trustMe[p2].push(p1)
        
    }
    
    for( let i=1; i<trustYou.length; i++) {
        if( trustYou[i].length === 0 && trustMe[i].length === N-1) {
            return i
        }
    }
    
    return -1
};