[Leetcode] 721. Accounts Merge (C++)
문제
코드
class Solution {
public:
unordered_set<string> visited;
unordered_map<string, vector<string>> adj;
void dfs(vector<string>& merged, string& email){
visited.insert(email);
merged.push_back(email);
for (auto a : adj[email]){
if (visited.find(a) != visited.end()) continue;
dfs(merged, a);
}
}
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
for (auto account : accounts){
int sz = account.size();
for (int i = 2; i < sz; i++){
adj[account[1]].push_back(account[i]);
adj[account[i]].push_back(account[1]);
}
}
vector<vector<string>> merged;
for (auto account : accounts){
string name = account[0];
string first = account[1];
if (visited.find(first) == visited.end()){
vector<string> temp;
temp.push_back(name);
dfs(temp, first);
sort(temp.begin()+1, temp.end());
merged.push_back(temp);
}
}
return merged;
}
};
접근
같은 이메일을 사용할 경우 두 계정이 같은 사람에게 속하기 때문에 모든 메일들을 살펴보면서 메일 간의 관계를 확인해주었다. 이를 기반으로 같은 메일들을 dfs로 찾아서 추가해 줄 수 있었고 set을 이용해서 이미 확인한 메일도 체크해 주어서 같은 이메일이 여러 번 나올 경우를 차단했다.
Author And Source
이 문제에 관하여([Leetcode] 721. Accounts Merge (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@keybomb/Leetcode-721.-Accounts-Merge-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)