[LC] 721. Accounts Merge

[seungriyou]

https://leetcode.com/problems/accounts-merge/

미디엄 맞나..? 😮‍💨😢😠💢

Approach

Idea 1: DFS

ref: https://leetcode.com/problems/accounts-merge/solutions/109161/python-simple-dfs-with-explanation

1. 다음과 같이 email을 기준으로 속하는 account의 idx를 모아 그래프를 구성한다.

   {email: [account idx]}

2. 모든 account에 대해 DFS를 수행하면서, 해당 account에 해당되는 email을 set()에 모은다.

   이때, visited 리스트를 이용하여 이미 확인된 account는 더이상 확인하지 않도록 함으로써 merge 동작을 수행한다!

3. 모은 결과를 [name] + sorted(list(set)) 으로 구성한다.

Idea 2: Union-Find

ref: https://leetcode.com/problems/accounts-merge/solutions/1084738/python-the-clean-union-find-solution-you-are-looking-for

1. union-find를 통해 동일한 email을 가지는 account를 union 해나간다. (merge 동작)

   이때, 동일한 email을 가지는 account를 찾기 위해 ownership이라는 dict를 이용한다. 이는 accounts를 순회하면서 계속해서 업데이트 해나간다.

   {email: account idx}

2. union 결과와 ownership에 기록되어 있는 정보를 토대로 find를 수행해가며 최상위 부모 account를 찾아가며 결과를 구성한다. (w/ sorting)

[!tip] union-find를 클래스로 구현하면 parent와 같은 필드를 내부에서 관리할 수 있다!

[!note] ranking을 이용하면 path compression을 적용한 union-find를 O(n)에서 O(logn)으로 최적화 할 수 있다는 것 같은데... 추후에 알아보도록 하자..

ref: LINK1 / LINK2

Complexity

• Time: O(nm * log(nm)) (n = # of accounts, m = # of emails per account)
• Space: (dfs) O(nm) / (union-find) O(n) (result 제외)