[LeetCode] Find the Town Judge

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

Find the Town Judge - LeetCode

 

마을의 판사를 찾는 문제! 

 

판사는 다음과 같은 규칙으로 찾을 수 있다. 

 

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

2. 판사를 제외한 사람들은 모두 판사를 믿는다. 

3. n명 중에서는 위 1,2 조건을 가진 사람이 한 명 이상은 있다. 

 

즉 n-1명이 본인을 믿고, 본인은 아무도 믿지 않아야 하는 것입니다. 

 

처음에는 dictionary로 접근했으나 이후 효율적인 풀이를 보니 기본 배열 두 개를 사용해서 값을 얻어낸 것을 알 수 있었습니다. 

우선 제가 짠 코드를 먼저 보죠!

 

class Solution {
    func findJudge(_ n: Int, _ trust: [[Int]]) -> Int {
        // 키 값이 없어야 함. 판사의 벨류값은 배열의 전체 길이 -1 이어야 함. 
        // 나 빼고 나머지가 날 믿어야 하기 때문 
        if n == 1 { return 1 }        
        var judge = -1
        if !trust.isEmpty {
            var relation = [Int:[Int]]()
            for t in trust {            
                let sender = t[0]
                let receiver = t[1]         
                if let val = relation[receiver] {
                    relation[receiver]!.append(sender)               
                } else {
                    relation[receiver] = [sender]
                }

            }
            let trusted = relation.values.flatMap {$0}
            for (k,v) in relation {
                if !trusted.contains(k) && v.count == n - 1 {
                    judge =  k
                    break
                } 
            }
        }
        return judge
    }
}

 

지금 보니... 변수 선언한게 많긴 하네요.. 이 부분에서 불필요한 메모리 할당이 발생한 것 같네요. 

우선 간단히 보자면, trust 배열을 [sender, receiver]로 보고 관계를 딕셔너리에 추가해줍니다. 

이후 판사를 찾기 위해, 모두가 나를 믿는지, 나는 아무도 믿지 않고 있는지를 확인해줍니다. 

 

이 두 가지 조건이 핵심이기에 이것만 이용한다면 더 쉽게 풀 수 있을 것 같습니다. 

 

class Solution {
    func findJudge(_ n: Int, _ trust: [[Int]]) -> Int {
        var receive = Array(repeating: 0, count: n+1) 
        var send = Array(repeating: 0, count: n+1) 
        
        for t in trust {
            receive[t[1]] += 1
            send[t[0]] += 1
        }
        
        for p in 1...n {
            if receive[p] == n - 1 && send[p] == 0 { 
                return p
            }
        }
        
        return -1 
    }
}

receive와 send라는 배열을 통해 누가 몇 명을 믿고, 믿음을 받고 있는지를 카운트해줍니다. 

그리고 조건에 맞는지 확인 후 그 사람이 판사라는 것을 반환해주면 됩니다!

나머지 경우는 다 답이 없는 케이스이기 때문에 -1을 리턴해주면 됩니다! 

 

그래프 중 간단한 문제!

 

끄읕