LeetCode 2285 solution

problem

You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.

You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.

You need to assign each city with an integer value from 1 to n, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects.

Return the maximum total importance of all roads possible after assigning the values optimally.

Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output: 43
Explanation: The figure above shows the country and the assigned values of [2,4,5,3,1].
- The road (0,1) has an importance of 2 + 4 = 6.
- The road (1,2) has an importance of 4 + 5 = 9.
- The road (2,3) has an importance of 5 + 3 = 8.
- The road (0,2) has an importance of 2 + 5 = 7.
- The road (1,3) has an importance of 4 + 3 = 7.
- The road (2,4) has an importance of 5 + 1 = 6.
The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.
It can be shown that we cannot obtain a greater total importance than 43.

문제에서 중요한 것은 결국 얼마나 많이 해당 dot 등장했느냐 이다. 이에 대해서 나는 hash로 접근하려고 했다. hash 저장을 해둔 뒤에, 우선 sorting 진행한다. n 의 역순으로 결국 중요도가 부여된다. 6,5,4,3,2,1 이런 식으로 중요도가 부여된다. 그렇기에 sorting 이후에 다시 hash 에서 찾아와서 6부터 시작해서 부여해 줬다.

python

import operator
class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        hash_t = {}
        for r in roads:
            a,b = r[0], r[1]
            hash_t[a] = hash_t.get(a,0) + 1
            hash_t[b] = hash_t.get(b,0) + 1

        temp = sorted(hash_t.items(), key = operator.itemgetter(1,0), reverse=True)
        m = n
        for k,v in temp:
            hash_t[k] = m
            m -= 1

        result = 0
        for r in roads:
            a,b = r[0], r[1]
            result += hash_t[a] + hash_t[b]
        return result

다른 사람의 풀이를 보았을 때 그렇게 효율적인 코드는 아니지만, hash를 착실하게 활용하려 했다. 다른 사람의 풀이와의 가장 큰 차이는 *에 대한 활용으로 보였다. 다른 사람들은 가중치 그러니깐 중요도를 곱하기를 활용해서 효율적으로 부여했던 것에 비해서, 나의 코드는 계속해서 for loop + + 를 활용해서 조금 더 비효율적으로 보였다. 물론 구동은 똑같고, 복잡도도 동일하다. 다만 코드가 깔끔한 것에 대해서 해당 방식을 수용할 만하다고 생각했다.