accounts[i][0]은 사람의 이름, accounts[i][1]은 이메일을 나타내는 구조로 되어있다.
한 사람이 여러 개의 이메일을 소유하기도 하며, 동명이인이 존재할 수 있다. 이때 구분하는 방법은 다음과 같다.
이름이 동일하고, 이메일이 다르다면 동명이인이다.
이름이 동일하고, 이메일 중 동일한 이메일이 존재한다면 동일인이다.(복수의 이메일을 가진 사람)
이때 이메일 정보를 취합하여 출력하는 프로그램을 작성하라
문제 접근
처음 보면 난해해 보인다. 하지만 입력 부분을 잘 보면 그래프로 모델링할 수 있다.
위의 조건 중 하나로 이름이 같고, 이메일 중 동일한 이메일이 있다면 동일 사람이다라고 하는 조건을 잘 보자. 이는 동일한 이메일을 부모 노드로 하는 자식 노드들로 생각할 수 있다.
위 입력에서 "john@mail.com", "john_lab@mail.com"과 "john@mail.com", "john02@mail.com"은 "john@mail.com"이 데이터로 들어간 노드를 공통으로 하는 노드들로 생각할 수 있단 것이다.
그렇다면 위 규칙들을 통해 각각의 이름을 가지는 그래프들로 모델링할 수 있고, 이 그래프들을 순회함으로서 이메일 정보들을 취합할 수 있을것 같다.
import java.util.*;
public class Practice3 {
public static ArrayList<ArrayList<String>> solution(ArrayList<ArrayList<String>> accounts) {
}
public static void main(String[] args) {
// Test code
ArrayList<ArrayList<String>> accounts = new ArrayList<>();
accounts.add(new ArrayList<>(Arrays.asList("John", "john@mail.com", "john_lab@mail.com")));
accounts.add(new ArrayList<>(Arrays.asList("John", "john@mail.com", "john02@mail.com")));
accounts.add(new ArrayList<>(Arrays.asList("Mary", "mary@mail.com")));
accounts.add(new ArrayList<>(Arrays.asList("John", "johnnybravo@mail.com")));
accounts = solution(accounts);
for (ArrayList<String> item: accounts) {
System.out.println(item);
}
}
}
문제 풀이
우선 그래프 모델링 부터 시작해야 한다.
그래프는 Map 자료구조를 통해 구현하며 이메일과 그 이메일과 연결된 다른 이메일 노드들을 나타내야 한다.
또한 각 이메일의 소유자의 이름이 무엇인지를 저장해놓는 name 역시 Map 자료구조로 구현할 것이다.
public static ArrayList<ArrayList<String>> solution(ArrayList<ArrayList<String>> accounts) {
// {"이메일", 해당 이메일과 연결된 노드들(이메일들)} 로 되어있는 해시맵
HashMap<String, HashSet<String>> graph = new HashMap<>();
HashMap<String, String> name = new HashMap<>();
for (ArrayList<String> account : accounts){
String userName = account.get(0);
for (int i = 1; i < account.size(); i++){
if (!graph.containsKey(account.get(i))){
graph.put(account.get(i), new HashSet<>());
}
name.put(account.get(i), userName);
if (i == 1){
continue;
}
// 그래프 연결
graph.get(account.get(i)).add(account.get(i - 1));
graph.get(account.get(i - 1)).add(account.get(i));
}
}
}
입력으로 들어온 계정 정보를 하나씩 읽어 해당 이메일이 이미 그래프에 존재하는 이메일인지를 먼저 확인한다. 이후 존재하지않는다면 해당 이메일 정보를 가지는 노드를 생성하여 그래프에 추가시킨다.
이후 이름을 관리하는 Map인 name에도 이메일과 해당 이메일의 소유주를 넣어 저장시킨다.
이후 각 그래프의 연결을 수행한다. 한 행에 있는 이메일들은 모두 소유주가 동일하기 때문에 서로 인접해 있다고 보아도 무방하다. 따라서 직전 노드와 현재 노드를 서로 연결시켜준다.
그래프 모델링이 끝나면 이제 각 그래프들에 대해 DFS 탐색을 수행하면 된다.
public static ArrayList<ArrayList<String>> solution(ArrayList<ArrayList<String>> accounts) {
// {"이메일", 해당 이메일과 연결된 노드들(이메일들)} 로 되어있는 해시맵
HashMap<String, HashSet<String>> graph = new HashMap<>();
HashMap<String, String> name = new HashMap<>();
for (ArrayList<String> account : accounts){
String userName = account.get(0);
for (int i = 1; i < account.size(); i++){
if (!graph.containsKey(account.get(i))){
graph.put(account.get(i), new HashSet<>());
}
name.put(account.get(i), userName);
if (i == 1){
continue;
}
// 그래프 연결
graph.get(account.get(i)).add(account.get(i - 1));
graph.get(account.get(i - 1)).add(account.get(i));
}
}
// 방문 기록용
HashSet<String> visited = new HashSet<>();
ArrayList<ArrayList<String>> result = new ArrayList<>();
// 그래프에 저장된 모든 이메일들에 대해 방문하지 않았다면 DFS수행
for (String email: name.keySet()){
ArrayList<String> list = new ArrayList<>();
if (visited.add(email)){
dfs(graph, email, visited, list);
Collections.sort(list);
list.add(0, name.get(email));
result.add(list);
}
}
return result;
}
HashSet은 중복된 데이터가 입력으로 들어올 경우에 false를 반환한다. 따라서 add의 반환값을 사용하여 이미 방문하였는지를 검사할 수 있다.
이후 해당 이메일과 연결된 이메일들을 받은 리스트를 정렬하고, 해당 이메일들의 소유주를 맨 앞에 추가하여 result에 삽입한다.
이후 result를 반환하며 마무리된다.
public static void dfs(HashMap<String, HashSet<String>> graph, String email, HashSet<String> visited, ArrayList<String> list){
list.add(email);
for (String next: graph.get(email)){
if (visited.add(next)){
dfs(graph, next, visited, list);
}
}
}
dfs는 재귀적으로 구현하였다. 해당 이메일과 연결된 노드들을 순회하며 방문한 노드가 존재하는지 확인하고 방문하지 않았을 경우에 해당 노드를 방문하는 DFS의 로직 그대로를 구현하였다.
전체적인 코드는 다음과 같다.
import java.util.*;
public class Practice3 {
public static ArrayList<ArrayList<String>> solution(ArrayList<ArrayList<String>> accounts) {
HashMap<String, HashSet<String>> graph = new HashMap<>();
HashMap<String, String> name = new HashMap<>();
for (ArrayList<String> account : accounts){
String userName = account.get(0);
for (int i = 1; i < account.size(); i++){
if (!graph.containsKey(account.get(i))){
graph.put(account.get(i), new HashSet<>());
}
name.put(account.get(i), userName);
if (i == 1){
continue;
}
graph.get(account.get(i)).add(account.get(i - 1));
graph.get(account.get(i - 1)).add(account.get(i));
}
}
HashSet<String> visited = new HashSet<>();
ArrayList<ArrayList<String>> result = new ArrayList<>();
for (String email: name.keySet()){
ArrayList<String> list = new ArrayList<>();
if (visited.add(email)){
dfs(graph, email, visited, list);
Collections.sort(list);
list.add(0, name.get(email));
result.add(list);
}
}
return result;
}
public static void dfs(HashMap<String, HashSet<String>> graph, String email, HashSet<String> visited, ArrayList<String> list){
list.add(email);
for (String next: graph.get(email)){
if (visited.add(next)){
dfs(graph, next, visited, list);
}
}
}
public static void main(String[] args) {
// Test code
ArrayList<ArrayList<String>> accounts = new ArrayList<>();
accounts.add(new ArrayList<>(Arrays.asList("John", "john@mail.com", "john_lab@mail.com")));
accounts.add(new ArrayList<>(Arrays.asList("John", "john@mail.com", "john02@mail.com")));
accounts.add(new ArrayList<>(Arrays.asList("Mary", "mary@mail.com")));
accounts.add(new ArrayList<>(Arrays.asList("John", "johnnybravo@mail.com")));
accounts = solution(accounts);
for (ArrayList<String> item: accounts) {
System.out.println(item);
}
}
}
