Leetcode 721. Accounts Merge (Union Find)

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

Accounts Merge - LeetCode

 

---

 

또 다시 만난 Union Find 문제,,,,

 

하지만 다시 헤매고 문제의 취지에 맞지 않게 풀이를 작성한 제 풀이를 보며 반성하는 마음으로,,,풀이를 분석해보겠습니다

 

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        accounts.sort(key= lambda x: (-len(x),x[0],x[1]))
    
        temp = deque(accounts[1:])
        res = [accounts[0]]
            
        while temp:
            node = temp.popleft()
            if res[-1][0] == node[0] and len(list(set(res[-1]) & set(node))) != 1 :
                res[-1] += list(set(res[-1])-set(node))
                res[-1].extend(node)
                
            else:
                res.append(node)
        #return accounts
        return sorted([sorted(list(set(i))) for i in res],key=lambda x:(x[0]))

저는 deque를 활용해서 겹치는 부분을 뽑고 비교하고 합치고 하는 과정을 거치는 방법을 사용했는데요

시간도 많이 걸리고 에러가 계속 발생했습니다 ㅜㅠ

 

728x90

---

DFS 풀이 )

문제를 보고 가장 헤맸었던 부분은 어떻게 하면 주어진 INPUT자료를 GRAPH 형식으로 해석/사용할 수 있을까였습니다

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],
				["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

 

동명이인이 있을 수 있기 때문에 제일 앞 이름으로 GRAPH를 만들 수 없다고 생각했었는데 이 풀이를 보면서 답을 찾았습니다. (Source: Leetcode discussion yangshun)

 

이 풀이의 핵심은 graph의 중심을 각 이메일로 잡고 대응하는 값을 각 항의 인덱스 처리했는데요

[
  ["John", "johnsmith@mail.com", "john00@mail.com"], # Account 0
  ["John", "johnnybravo@mail.com"], # Account 1
  ["John", "johnsmith@mail.com", "john_newyork@mail.com"],  # Account 2
  ["Mary", "mary@mail.com"] # Account 3
]

 

위의 기존 input을 아래와 같이 Graph로 재구성한거죠!!!

 

{
  "johnsmith@mail.com": [0, 2],
  "john00@mail.com": [0],
  "johnnybravo@mail.com": [1],
  "john_newyork@mail.com": [2],
  "mary@mail.com": [3]
}

 

이제 코드를 보겠습니다

 

class Solution(object):
    def accountsMerge(self, accounts):
        from collections import defaultdict
        visited_accounts = [False] * len(accounts)
        emails_accounts_map = defaultdict(list)
        res = []
        
        # Graph 만들기
        for i, account in enumerate(accounts):
            for j in range(1, len(account)):
                email = account[j]
                emails_accounts_map[email].append(i)
                
        # DFS 함수 만들기
        
        def dfs(i, emails):
            if visited_accounts[i]:
                return
            visited_accounts[i] = True
            for j in range(1, len(accounts[i])):
                email = accounts[i][j]
                emails.add(email)
                for neighbor in emails_accounts_map[email]:
                    dfs(neighbor, emails)
                    
        # DFS 실행하기
        
        for i, account in enumerate(accounts):
            if visited_accounts[i]:
                continue
            name, emails = account[0], set()
            dfs(i, emails)
            res.append([name] + sorted(emails))
        return res

 

와 정말 구성이 깔끔하고 섬세하게 잘 연결된 코드인 것 같습니다 ㅜㅠ

 

특히 DFS 구성 부분이 이전에 만든 GRAPH의 키 부분을 이웃 리스트로 가지고 와서 다시 DFS를 재귀시키는 부분이 

어떻게 저런 발상을 했지 싶네요. 그리고 DFS의 결과값으로 쌓이는 EMAILS을 마지막에 가지고 와서 더해주는 부분까지!

심지어 emails을 중복을 없애기 위해 set으로 만들어준 부분도 참신한 것 같습니다

 

 

---

 

Union find 풀이 )

별도로 Union Find 함수를 만들면서 접근했는데요

#unionfind 기능 구현
class UF:
    def __init__(self, N):
        self.parents = list(range(N))
    def union(self, child, parent):
        self.parents[self.find(child)] = self.find(parent)
    def find(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    
class Solution: 
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        uf = UF(len(accounts))
 #parents를 구성하는 N 제공
        
        ownership = {}
        for i, (_, *emails) in enumerate(accounts):
            for email in emails:
                if email in ownership:
                    uf.union(i, ownership[email])
                ownership[email] = i
        
        ans = collections.defaultdict(list)
        for email, owner in ownership.items():
            ans[uf.find(owner)].append(email)
        
        return [[accounts[i][0]] + sorted(emails) for i, emails in ans.items()]

 

접근 방식은 dfs와 같지만 함수로 만들어서 기능이 좀 더 가시적으로 보이도록 했습니다.

 

이 문제의 Union find를 시각화해서 보고 싶다면 이 링크를 참고해주세요

https://leetcode.com/problems/accounts-merge/discuss/1602535/Full-Explanation-DRY-RUN-on-first-example-Code-with-comments-simple-variables-name-C%2B%2B-!!!

 

 

 

Union Find 관련 설명과 다른 예제를 보고 싶다면 아래를 참고해주세요 ↓ ↓ ↓ ↓

 

2022.09.27 - [ERROR RECORD] - Leetcode 200. Number of Islands (Union Find)

2022.09.26 - [Data Structure & Algorithm] - Union Find