숫자 n, 'languages'라는 배열, 'friendships'라는 배열이 있고 1부터 n까지 번호가 매겨진 n개의 언어가 있다고 가정하고, languages[i]는 i번째 사용자가 알고 있는 언어 집합을 나타내고, 우정[ i]는 쌍을 가지고 있습니다. [ui, vi]는 사용자 ui와 vi 사이의 우정을 나타냅니다. 우리는 하나의 언어를 선택하고 일부 사용자에게 가르칠 수 있으므로 모든 친구들이 서로 의사소통할 수 있습니다. 가르치는 데 필요한 최소 사용자 수를 찾아야 합니다. (우정은 전이가 아니라는 점을 명심해야 합니다. 따라서 x가 y의 친구이고 y가 z의 친구라고 해서 x가 z의 친구라는 의미는 아닙니다.)
따라서 입력이 다음과 같으면 n =3개 언어 =[[2],[1,3],[1,2],[3]] 우정 =[[1,4],[1,2],[3 ,4],[2,3]]인 경우 사용자 1과 3에 대해 언어 3을 교육해야 하므로 출력은 2가 됩니다. 가르칠 사용자가 두 명이므로 출력은 2입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- lang :=사용자가 알고 있는 모든 고유한 언어 집합의 목록
- not_comm :=새로운 세트
- 각 쌍에 대해, b 우정의 경우, do
- a :=a - 1
- b :=b - 1
- lang[a]와 lang[b]가 분리되어 있으면
- not_comm에 삽입
- not_comm에 b 삽입
- not_comm이 비어 있으면
- 0을 반환
- cnt :=빈 지도
- not_comm의 각 사람에 대해 다음을 수행합니다.
- lang[person]의 빈도를 저장하고 cnt에 저장
- temp :=cnt의 모든 값 목록의 최대값
- not_comm - temp의 반환 크기
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import Counter def solve(n, languages, friendships): lang = [set(L) for L in languages] not_comm = set() for a,b in friendships: a -= 1 b -= 1 if lang[a].isdisjoint(lang[b]): not_comm.add(a) not_comm.add(b) if not not_comm: return 0 cnt = Counter() for person in not_comm: cnt.update(lang[person]) temp = max(cnt.values()) return len(not_comm) - temp n = 3 languages = [[2],[1,3],[1,2],[3]] friendships = [[1,4],[1,2],[3,4],[2,3]] print(solve(n, languages, friendships))
입력
3, [[2],[1,3],[1,2],[3]], [[1,4],[1,2],[3,4],[2,3]]
출력
2