문제 설명
숫자 n, 배열 languages, 배열 friendships가 주어진다고 가정해 봅시다. 여기서 n은 1부터 n까지 번호가 매겨진 언어의 개수를 의미하고, languages[i]는 i번째 사용자가 아는 언어들의 집합을 나타내며, friendships[i]는 [ui, vi] 형태의 쌍으로 사용자 ui와 vi 사이의 우정 관계를 나타냅니다.
우리는 하나의 언어를 선택해 일부 사용자에게 가르칠 수 있으며, 이를 통해 모든 친구 관계에 있는 사람들이 서로 소통할 수 있도록 만들어야 합니다. 목표는 가르쳐야 할 사용자의 최소 수를 구하는 것입니다.
단, 우정 관계는 전이적(transitive)이지 않다는 점에 유의해야 합니다. 즉, x가 y의 친구이고 y가 z의 친구라고 해서 x와 z가 반드시 친구인 것은 아닙니다.
예시
입력이 다음과 같다고 가정해 보겠습니다.
n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
이 경우 출력은 2가 됩니다. 사용자 1과 사용자 3에게 언어 3을 가르치면 모든 친구가 소통할 수 있게 되고, 가르쳐야 할 사용자가 두 명이므로 결과는 2입니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- lang: 각 사용자가 아는 언어들의 집합(set)을 담은 리스트를 생성합니다.
- not_comm: 서로 소통할 수 없는 사용자를 저장할 새로운 집합을 생성합니다.
- friendships의 각 쌍 (a, b)에 대해 다음을 수행합니다.
- a := a - 1, b := b - 1 (0 기반 인덱스로 변환)
- lang[a]와 lang[b]가 서로소(disjoint), 즉 공통 언어가 없다면:
- a를 not_comm에 추가
- b를 not_comm에 추가
- not_comm이 비어 있다면 0을 반환합니다. (모든 친구가 이미 소통 가능)
- cnt: 빈 카운터(맵)를 생성합니다.
- not_comm에 있는 각 사용자에 대해 해당 사용자가 아는 언어들의 빈도수를 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
복잡도 분석
시간 복잡도는 O(F×L + U×L)입니다. 여기서 F는 친구 관계의 수, U는 소통 불가능한 사용자의 수, L은 사용자당 평균 언어 수입니다. 공간 복잡도는 소통 불가능한 사용자를 저장하는 데 필요한 O(U)입니다.