[릿코드 721] Accounts Merge (파이썬/python)

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

Accounts Merge - LeetCode

 

 

1. Map 안에 각 이름별로 메일링 리스트를 만들었다.

 

만든다음 set 으로 중복을 없애고, 현재 보고있는 메일리스트와 비교대상 리스트를 더해서 다시 set 으로 만들어준다.

set 으로 만들어줬을때 길이가 줄어든다면 중복된 이메일이 있다는 뜻이고, 연결된 계정이라는 뜻이다.

 

2. 출제의도인것 같은 dfs 풀이

각각의 accounts 들의 인덱스를 이용해서

각각의 메일이 어떤 인덱스에 들어가있는지 딕셔너리에 매핑해준다.

 

그 후 순차적으로 accounts 를 순회하며 어떤 메일들이 연결되어있는지 dfs 탐색을 해주면 됨.

 

 

1번 풀이

from typing import *


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        dic_group_by_name = self.accountsToMap(accounts)

        self.checkEqualAcount(dic_group_by_name)

        return self.printResultBySort(dic_group_by_name)

    def accountsToMap(self, accounts: List[List[str]]) -> Dict[str, List[List[str]]]:
        dic_group_by_name = {}

        for account in accounts:
            mails_not_dup = list(set(account[1:]))

            if account[0] in dic_group_by_name:
                dic_group_by_name[account[0]].append(mails_not_dup)
            else:
                dic_group_by_name[account[0]] = [mails_not_dup]

        return dic_group_by_name

    def checkEqualAcount(self, dic_group_by_name: Dict[str, List[List[str]]]):

        for key in dic_group_by_name.keys():
            mail_list_for_the_same_name = dic_group_by_name.get(key)

            for i in range(len(mail_list_for_the_same_name)):
                mail_list = mail_list_for_the_same_name[i]

                for j in range(i + 1, len(mail_list_for_the_same_name)):
                    comparison_target = mail_list_for_the_same_name[j]

                    mail_not_dup = list(set(comparison_target + mail_list))

                    if len(mail_not_dup) != len(mail_list) + len(comparison_target):
                        mail_list_for_the_same_name[j] = mail_not_dup
                        mail_list_for_the_same_name[i] = []
                        break

    def printResultBySort(self, dic_group_by_name: Dict[str, List[List[str]]]) -> List[List[str]]:
        result = []

        for key in dic_group_by_name.keys():
            mail_list_for_the_same_name = dic_group_by_name.get(key)

            for mail_list in mail_list_for_the_same_name:
                if mail_list:
                    result.append([key] + sorted(mail_list))

        return result

 

 

2번 풀이

from typing import List


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        visit = [False] * len(accounts)
        result = []

        mail_idx_dic = self.mailIdxToDic(accounts)

        for i, account in enumerate(accounts):
            if visit[i]:
                continue

            name, emails = account[0], set()
            self.dfs(visit, mail_idx_dic, i, emails, accounts)
            result.append([name] + sorted(emails))

        return result

    def mailIdxToDic(self, accounts):
        mail_idx_dic = {}

        for i, account in enumerate(accounts):
            for j in range(1, len(account)):
                email = account[j]
                if email in mail_idx_dic:
                    mail_idx_dic[email].append(i)
                else:
                    mail_idx_dic[email] = [i]

        return mail_idx_dic

    def dfs(self, visit, mail_idx_dic, i, emails, accounts):
        if visit[i]:
            return

        visit[i] = True

        for j in range(1, len(accounts[i])):
            email = accounts[i][j]
            emails.add(email)

            for neighbor in mail_idx_dic[email]:
                self.dfs(visit, mail_idx_dic, neighbor, emails, accounts)