[LeetCode] 1615. Maximal Network Rank

📃 문제 설명

(MEDIUM) https://leetcode.com/problems/maximal-network-rank/

• bidirectional graph에서 두 vertex를 골랐을 때, 해당 vertex들과 연결된 edge들 갯수의 최대값이 무엇인지를 묻는 문제이다.

🔎 문제 접근

• 각 vertex에 대해 연결된 edge들이 몇 개인지 파악하고, 해당 값을 max sorting하여 상위 두 개의 값을 뽑아 더하면 된다.
• 다만, 선택된 두 vertex가 서로 연결되어 있을 경우에는 더한 값에서 1을 빼줘야 하기 때문에 (중복 count) 다음과 같은 고려를 해줘야 한다.
  • 연결된 edge의 최대값에 해당하는 vertex가 2개 이상일 경우:
    • vertex들 중 두 개를 골랐을 때, 연결되지 않았을 경우가 발견된 경우에는 max * 2 를 반환
    • 모든 경우에 대해 두 vertex 쌍이 연결되어 있을 경우에는 max * 2 - 1 를 반환
  • 연결된 edge에 최대값에 해당하는 vertex가 1개일 경우:
    • 두 번째 최대값에 해당하는 vertex들과 연결되었는지 여부를 파악해,
    • max + max2 또는 max + max2 - 1 를 반환

✨ 문제 풀이

from itertools import combinations

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        #연결된 도로가 0개거나 1개일 경우 각각 0, 1을 반환
        if len(roads) == 0:
            return 0
        
        if len(roads) == 1:
            return 1
        
        num_connected = [0] * n #각 vertex에서 연결된 edge를 센다
        graph = [[False] * n for _ in range(n)] #vertex i와 j가 연결되었는지 여부를 확인
        
        for a, b in roads:
            num_connected[a] += 1
            num_connected[b] += 1
            graph[a][b] = True
            graph[b][a] = True
        
        #n이 100 이하로 작기 때문에, counting sort를 응용해서 sorting 진행
        num_sorted_connect = [[] for _ in range(n)]
        #edge 연결 갯수의 최대값 두 개를 저장 
        max_connect = [-1, -2]
        
        for idx, el in enumerate(num_connected):
            num_sorted_connect[el].append(idx)
            if el > max_connect[0]:
                max_connect[1] = max_connect[0]
                max_connect[0] = el
            elif el == max_connect[0]:
                continue
            elif el > max_connect[1]:
                max_connect[1] = el
        
        #최대값에 해당하는 vertex가 2개 이상일 경우, 해당 vertex끼리 combinations 진행
        if len(num_sorted_connect[max_connect[0]]) >= 2:
            for i, j in combinations(num_sorted_connect[max_connect[0]], 2):
                if not graph[i][j]:
                    return max_connect[0] * 2
            return max_connect[0] * 2 - 1
        else: #최대값에 해당하는 vertex가 1개일 경우, 두 번째 최대값에 해당하는 vertex와 연결 여부를 확인
            i = num_sorted_connect[max_connect[0]][0]
            for j in num_sorted_connect[max_connect[1]]:
                if not graph[i][j]:
                    return max_connect[0] + max_connect[1]
            return max_connect[0] + max_connect[1] - 1        

• redundancy를 줄이기 위해 max_connect , counting sort 등을 활용하기는 했지만 빠르기가 97% 정도라니 약간 신기했다.