[LeetCode] 721. Accounts Merge

😎풀이

1. 메일을 순회
   1-1. 각 메일의 소유자를 기록
   1-2. 메일을 기준으로 그룹화 하여 root 메일 선정
2. 각 사용자에게 알맞는 메일을 오름차 순으로 정렬하여 할당

function accountsMerge(accounts: string[][]): string[][] {
    const parent = new Map<string, string>()
    const emailToName = new Map<string, string>()

    const find = (email: string) => {
        if(!parent.has(email)) {
            parent.set(email, email)
        } 
        if(parent.get(email) !== email) {
            parent.set(email, find(parent.get(email)))
        }
        return parent.get(email)
    }

    const union = (email1: string, email2: string) => {
        const root1 = find(email1)
        const root2 = find(email2)
        if(root1 === root2) return
        parent.set(root1, root2)
    }

    for(const [name, ...emails] of accounts) {
        const firstMail = emails[0]
        for(const email of emails) {
            emailToName.set(email, name)
            union(email, firstMail)
        }
    }

    const groups = new Map<string, string[]>()
    for(const email of emailToName.keys()) {
        const root = find(email)
        groups.set(root, [...(groups.get(root) ?? []), email])
    }
    
    const result = []
    for(const [root, emails] of groups) {
        const sortedEmails = emails.toSorted()
        const name = emailToName.get(root)!;
        result.push([name, ...sortedEmails]);
    }

    return result
};