[Trees: Union Find] 721. Accounts Merge ★★★★★★★★

721. Accounts Merge

 

이 문제는 Union-Find(Disjoint Set) 을 사용하는 대표적인 그래프 문제입니다.
각 이메일을 노드로 보고, 같은 사람의 이메일끼리 연결(merge) 해주는 방식입니다.

---

✅ 문제 핵심 정리

• accounts[i][0]: 이름 (예: "John")
• accounts[i][1:]: 이메일 주소들
• 공통 이메일이 있으면 같은 사람 → 이메일들을 하나의 집합으로 merge
• 결과는 [이름, 정렬된 이메일 목록] 형식으로 반환

---

✅ 전략

1. Union-Find 구조 생성
2. 이메일 간 연결을 Union-Find로 묶기
3. 각 이메일의 루트를 기준으로 그룹핑
4. 이름을 이메일과 매핑해 최종 결과 구성

---

✅ 전체 코드 (풀 구현 + 설명 주석)

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        # 1. Union-Find 초기화
        # 각 계정(리스트 index)을 자기 자신이 부모로 시작
        par = [i for i in range(len(accounts) + 1)]  # 부모 노드 배열
        rank = [1] * (len(accounts) + 1)             # 트리의 깊이 또는 크기 추정치

        # 2. Find 함수 (경로 압축 적용)
        def find(n):
            p = par[n]  # 현재 노드의 부모

            # 루트 노드가 아니면 계속 따라 올라감
            while p != par[p]:
                par[p] = par[par[p]]  # 중간 부모를 루트의 손자 노드로 압축
                p = par[p]            # 루트로 향하는 방향으로 계속 이동
            return p  # 루트 노드 반환

        # 3. Union 함수 (Rank 기반으로 병합)
        def union(n1, n2):
            p1, p2 = find(n1), find(n2)  # 두 노드의 루트를 찾음

            if p1 == p2:
                # 이미 같은 집합이면 병합하지 않음 (사이클 방지)
                return False

            # 랭크가 더 큰 루트 쪽으로 작은 쪽을 병합
            if rank[p1] > rank[p2]:
                par[p2] = p1            # p2의 루트를 p1으로
                rank[p1] += rank[p2]    # p1의 랭크에 p2의 랭크를 더함
            else:
                par[p1] = p2            # p1의 루트를 p2로
                rank[p2] += rank[p1]    # p2의 랭크에 p1의 랭크를 더함
            return True  # 새로운 병합이 일어남을 표시

        # 4. 이메일 → 계정 index 매핑 / 이메일 → 이름 매핑
        email_to_id = {}    # 각 이메일이 속한 최초의 계정 index 저장
        email_to_name = {}  # 각 이메일의 주인 이름 저장

        for i, acc in enumerate(accounts):  # 계정 리스트 순회
            name = acc[0]  # 첫 번째 항목은 이름

            for email in acc[1:]:  # 이메일들만 순회
                email_to_name[email] = name  # 이메일의 이름 저장

                if email in email_to_id:
                    # 이미 등장한 이메일이면, 현재 계정 i와 기존 계정 union
                    union(i, email_to_id[email])
                else:
                    # 처음 본 이메일이면 현재 계정 index를 저장
                    email_to_id[email] = i

        # 5. 루트 기준으로 이메일들을 묶어 그룹핑
        from collections import defaultdict
        groups = defaultdict(list)  # 루트 index → 이메일 리스트

        for email, idx in email_to_id.items():  # 모든 이메일과 계정 index 순회
            root_id = find(idx)                 # 해당 계정의 대표 루트 찾기
            groups[root_id].append(email)       # 루트 기준으로 이메일을 묶음

        # 6. 최종 결과 구성
        res = []
        for idx, emails in groups.items():  # 루트 index별로 그룹 순회
            name = email_to_name[emails[0]]      # 아무 이메일에서 이름 가져오기
            res.append([name] + sorted(emails))  # 이름 + 정렬된 이메일 리스트

        return res  # 병합된 결과 리스트 반환

 

✅ 예시 설명

입력:

["John","johnsmith@mail.com","john_newyork@mail.com"], ["John","johnsmith@mail.com","john00@mail.com"]

• 두 리스트는 "johnsmith@mail.com"을 공유하므로 → 같은 사람
• Union-Find로 같은 집합으로 묶음
• 결과:

["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"]

---

✅ 시간 복잡도

• 초기화 + union: O(N·α(N))
• 그룹핑 및 정렬: O(N·logN)
• 전체적으로 매우 빠름

https://youtu.be/6st4IxEF-90