설명

각 요소accounts는 문자열 목록이고 첫 번째 요소accounts[i]는 이름이고 나머지 요소는 계정의 이메일을 나타내는 이메일인 accounts[i][0] 목록이 주어집니다.

이제 이 계정을 병합하려고 합니다. 두 계정에 공통 이메일이 있는 경우 두 계정은 분명히 같은 사람에게 속합니다. 두 계정의 이름이 같더라도 사람들이 같은 이름을 가질 수 있으므로 다른 사람에게 속할 수 있습니다. 한 사람이 처음에 여러 개의 계정을 가질 수 있지만 모든 계정의 이름은 확실히 동일합니다.

계정을 병합한 후 다음 형식으로 계정을 반환합니다. 각 계정의 첫 번째 요소는 이름이고 나머지 요소는 정렬된 순서대로 이메일입니다. 계정 자체는 어떤 순서로든 반환될 수 있습니다.

예 1:

Input: accounts = [["John","[email protected]","[email protected]"],["John","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]
Output: [["John","[email protected]","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]
Explanation:
The first and second John's are the same person as they have the common email "[email protected]".
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', '[email protected]'], ['John', '[email protected]'], 
['John', '[email protected]', '[email protected]', '[email protected]']] would still be accepted.

예 2:

Input: accounts = [["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
Output: [["Ethan","[email protected]","[email protected]","[email protected]"],["Gabe","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]

제약:

1 <= accounts.length <= 1000

2 <= accounts[i].length <= 10

1 <= accounts[i][j] <= 30

accounts[i][0] 영문으로 구성됩니다.

accounts[i][j] (for j > 0) 유효한 이메일입니다.

솔루션

솔루션 1

직관

유니온 찾기

암호

class Solution {

    private class UnionFind {
        int[] p;

        public UnionFind(int n) {
            p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = i;
            }
        }

        public int find(int x) {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        }

        public void union(int a, int b) {
            p[find(a)] = find(b);
        }
    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int n = accounts.size();
        UnionFind uf = new UnionFind(n);

        Map<String, Integer> emailWithOwnerIndex = new HashMap<>();

        for (int index = 0; index < n; index++) {
            List<String> account = accounts.get(index);
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                if (emailWithOwnerIndex.containsKey(email)) {
                    uf.union(index, emailWithOwnerIndex.get(email));
                } else {
                    emailWithOwnerIndex.put(email, index);
                }
            }
        }

        Map<Integer, List<String>> ownerIndexWithEmails = new HashMap<>();
        for (String email : emailWithOwnerIndex.keySet()) {
            int ownerIndex = uf.find(emailWithOwnerIndex.get(email));
            List<String> emails = ownerIndexWithEmails.getOrDefault(uf.find(ownerIndex), new ArrayList<String>());
            emails.add(email);
            ownerIndexWithEmails.put(ownerIndex, emails);
        }

        List<List<String>> ans = new ArrayList<>();
        for (int index : ownerIndexWithEmails.keySet()) {
            List<String> emails = ownerIndexWithEmails.get(index);
            Collections.sort(emails);
            emails.add(0, accounts.get(index).get(0));
            ans.add(emails);
        }
        return ans;
    }
}

const int N = 1001;
class Solution {
private:
    int p[N];

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        for (int i = 0; i < n; i++) p[i] = i;

        // email -> user indexes
        unordered_map<string, vector<int>> hash;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < accounts[i].size(); j++) {
                hash[accounts[i][j]].push_back(i);
            }
        }
        // union account indexes
        for (auto& [email, accountIndexes] : hash) {
            for (int i = 1; i < accountIndexes.size(); i++) {
                p[find(accountIndexes[i])] = p[find(accountIndexes[0])];
            }
        }
        // sorting the emails for each account
        vector<set<string>> emails(n);
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < accounts[i].size(); j++) {
                emails[find(i)].insert(accounts[i][j]);
            }
        }

        vector<vector<string>> res;
        for (int i = 0; i < n; i++) {
            if (!emails[i].empty()) {
                vector<string> account;
                account.push_back(accounts[i][0]);
                for (auto& email : emails[i]) account.push_back(email);
                res.push_back(account);
            }
        }
        return res;

    }
};

복잡성

시간: O(nlogn)

스페이스: O(n)