Leetcode 1733. Minimum Number of People to Teach

문제

On a social network consisting of m users and some friendships between users, 
two users can communicate with each other if they know a common language.

You are given an integer n, an array languages, and an array friendships where:

There are n languages numbered 1 through n,
languages[i] is the set of languages the i​​​​​​th​​​​ user knows, and
friendships[i] = [u​​​​​​i​​​, v​​​​​​i] denotes a friendship between the users u​​​​​​​​​​​i​​​​​ and vi.
You can choose one language and teach it to some users so that all friends can communicate with each other. Return the minimum number of users you need to teach.

Note that friendships are not transitive, meaning if x is a friend of y and y is a friend of z, this doesn't guarantee that x is a friend of z.

• 1~n 의 번호를 가진 사용자가 있다.
• 주어진 languages는 1~n번 사용자가 알고 있는 언어들의 목록이다.
• friendships는 1~n번 사용자들끼리 맺고 있는 인간관계이다.

이때

• 특정 언어 i에 대해서 서로 공유하는 언어를 알고 있지 않는 인간관계를 가진 사람들에게 i 언어를 가르칠때
• 최소한으로 언어를 가르쳐도 되는 i를 찾으시오

---

예시

n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]

• 사용자 1번에게 2언어를 가르치면 된다.
• 정답 : 1

---

제한

• $2 <= n <= 500$
• $languages.length == m$
• $1 <= m <= 500$
• $1 <= languages[i].length <= n$
• $1 <= languages[i][j] <= n$
• $1 <= u_i < v_i <= languages.length$
• $1 <= friendships.length <= 500$
• friendship의 모든 튜플은 유일하다.
• languages[i] 안의 값들도 유일하다.

---

풀이

1. 일단 관계들중 공통된 언어를 가진 것을 제외한다.
2. 그 후 남은 사람들이 알고 있는 언어를 각각 카운트 한다.
3. 모든 화자의 수 - 가장 많이 알고 있는 언어의 수

• 해당 계산시 가장 많이 알고 있는 언어는 곧 가장 적게 가르쳐도 되는 언어이기에, 가장 적게 가르치는 수가 나온다.

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
        languages = [set(langs) for langs in languages]

        learner = set()

        for a, b in friendships:
            a, b = a - 1, b - 1

            if not (languages[a] & languages[b]):
                learner.add(a)
                learner.add(b)

        count = [0] * (n + 1)

        for person in learner:
            for lang in languages[person]:
                count[lang] += 1

        return len(learner) - max(count)

---

여담

• 제발 1-index좀 쓰지 말았으면!@!!!