오늘의 문제
https://leetcode.com/problems/find-the-town-judge/
topological sort
이론으로 정리할 수 있는 특징
- directed graph 방향성이 있어야 한다. (단방향)
- unweighted edges 간선이동시 숫자나 비용이 없다.
- source : 나가는것만 있는 노드, 즉 목적지만 존재하는 노드
- sink : 들어오는것만 있는 노드, 즉 출발지만 존재하는 노드
How?
data structure -> BFS OR DFS 모두 가능
pseodo
- 주어진 array를 그래프(tree) 모양으로 바꾸어서 이해한다.
- 필요시 map 형태로 정의한다. 이 문제에서는 마을 판사를 찾기 위해 모든 마을 구성원들에 대한 destination , incoming 값을 조회하여 찾는다.
- 판사는 아무도 믿지 않으므로, sink node이다. 또한 incoming이 판사를 제외한 모든 구성원들에게 신뢰받아야 한다.
/**
edge case:
trust.length == 0 -> return -1
2.Brute force
ㄴ '믿는다 trust'를 화살표 (단방향이동)으로 볼때,
town judge는 아무도 믿지 않으므로 (나가는 화살표가 없으므로) sink 이다.
따라서, map 형태로 구현해놓고 조회하며 sink를 찾으면 될 것이다.
+ sink의 incoming 수 == n-1 이어야 함. 판사 본인을 제외한 전체 인원.
// key: 사람인덱스, val: { dest: 도착지의 개수(즉 본인이 믿는 사람의 인원수), incoming: 화살표로 들어오는 수 }
map = {
1 : {dest : 1, imcomimg: 0},
2 : {dest : 1, imcomimg: 0},
3 : {dest : 0, imcomimg: 2}, => pick !
}
for(map.length) {
if (dest == 0 && incoming == n-1){
return key;
}
}
return -1;
3.Optimal Solution
4. Real Code
5. Complexity
- time O(N)
- space O(N)
*/
class Solution {
public int findJudge(int n, int[][] trust) {
if (trust.length == 0){
if (n == 1) return n;
else return -1;
}
HashMap<Integer, TopologicalSort> map = new HashMap<>();
for (int[] persons : trust) {
if (!map.containsKey(persons[0])) map.put(persons[0], new TopologicalSort());
if (!map.containsKey(persons[1])) map.put(persons[1], new TopologicalSort());
TopologicalSort curr = map.get(persons[0]);
curr.destCnt++;
curr = map.get(persons[1]);
curr.incoming++;
}
for(Integer key:map.keySet()){
if (map.get(key).destCnt == 0 && map.get(key).incoming == n-1) return key;
}
return -1;
}
}
class TopologicalSort {
int destCnt;
int incoming;
public TopologicalSort() {
this.destCnt = 0;
this.incoming = 0;
}
}
풀이 이후
일단은 생각한 대로 코드로 구현하는 것은 성공했지만, 알고리즘의 이론대로 효율적인 구현을 위해서는 조금 더 생각해보고 싶다.