[leetcode] 1791. Find Center of Star Graph

• 참고

---

There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.

You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph.

Example 1:

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.
Example 2:

Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1

Constraints:

3 <= n <= 105
edges.length == n - 1
edges[i].length == 2
1 <= ui, vi <= n
ui != vi
The given edges represent a valid star graph

---

내 풀이

• 타임아웃 : 14분

// context
// 배열 내 중심 노드 탐색하여 return 하는 함수
// 기능 목록
// edges 길이만큼 탐색 반복
// edges 길이만큼 contain 되는 요소 저장
// 저장된 값 return
class Solution {
    public int findCenter(int[][] edges) {
        int center = 0;
        int target = 0;


        // edges 길이만큼 탐색 반복
        for (int i = 0; i < edges.length; i++) {
            for (int j = 0; j < edges.length; j++) {
                target = edges[i][j];
                // edges 길이만큼 contain 되는 요소 저장
                boolean valid = Arrays.asList(edges).containsAll(Arrays.asList(target));
                // target이 모든 배열에 포함되어 있으면 true return
                if (valid) {
                    center = target;
                }
            }
        }
        
        return center;
    }
}

결과

Runtime Error
java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
  at line 14, Solution.findCenter
  at line 56, __DriverSolution__.__helper__
  at line 86, __Driver__.main

다른 분의 풀이

• array

class Solution {
    public int findCenter(int[][] edges) {
        int a = edges[0][0];
        int b = edges[0][1];
        int c = edges[1][0];
        int d = edges[1][1];

        if (a==c || a == d) return a;
        return b;
    }
}

• hashtable
• O(n)

class Solution {
    public int findCenter(int[][] edges) {
        int n = Integer.MIN_VALUE;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < edges.length; i++) {
            map.put(edges[i][0],map.getOrDefault(edges[i][0],0)+1);
            map.put(edges[i][1],map.getOrDefault(edges[i][1],0)+1);
            n = Math.max(edges[i][0], n);
            n = Math.max(edges[i][1], n);
        }

        System.out.println(map);
        for(Map.Entry<Integer, Integer> e : map.entrySet()) {
            if(e.getValue() == n-1){
                return e.getKey();
            }
        }
        return 0;
    }
}

• 그리디

class Solution {
    public int findCenter(int[][] edges) {
        // 최대 시간에 발생하는 정점이 중심이므로 정점을 발생 횟수와 함께 저장하는 해시맵 생성
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < edges.length;i++) {
            for(int j=0; j<edges[0].length; j++){
                if(!map.containsKey(edges[i][j])) {
                    map.put(edges[i][j], 1);
                }
                int of=map.get(edges[i][j]);
                of=of+1;
                map.put(edges[i][j], of);
            }
        }

        int center = 0;
        int max = Integer.MIN_VALUE;
        for(int key:map.keySet()){
            if(map.get(key)>max){
                max=map.get(key);
                center=key;
            }
        }

        return center;
    }
}

• 그리디 4줄, 시간복잡도 O(n)

class Solution {
    public int findCenter(int[][] edges) {
        
        Set<Integer> set = new HashSet<>();
        set.add(edges[0][0]);
        set.add(edges[0][1]);
        return set.contains(edges[1][0]) ? edges[1][0] : edges[1][1];
    }
}