Python 연락처 목록에서 동일한 연락처 찾기

문제 상황

사용자 이름(username), 이메일(email), 전화번호(phone)를 임의의 순서로 저장하고 있는 연락처 목록이 있다고 가정해 보겠습니다. 이때 동일한 사람이 여러 개의 다른 연락처 정보를 가지고 있는 경우를 찾아, 같은 사람의 연락처들을 하나로 묶어 반환해야 합니다.

문제를 풀 때 다음 두 가지 조건을 염두에 두어야 합니다.

연락처 객체는 username, email, phone 필드를 어떤 순서로든 저장할 수 있습니다.
두 연락처는 동일한 username, 동일한 email, 또는 동일한 전화번호 중 하나라도 일치하면 같은 사람의 것으로 간주합니다.

입력 예시

cnt = [contact("Amal", "amal@gmail.com", "+915264"),
    contact("Bimal", "bimal321@yahoo.com", "+1234567"),
    contact("Amal123", "+915264", "amal_new@gmail.com"),
    contact("AmalAnother", "+962547", "amal_new@gmail.com")]

위 입력에 대한 출력은 다음과 같습니다.

0 2 3
1

인덱스 [0, 2, 3]에 있는 연락처들은 전화번호(+915264)나 이메일(amal_new@gmail.com)이 서로 연결되어 있으므로 같은 사람의 것이고, 인덱스 1의 연락처(Bimal)는 어느 것과도 일치하는 정보가 없어 별도의 그룹으로 분류됩니다.

풀이 접근 방식

이 문제는 각 연락처를 그래프의 노드로 보고, 공통 필드를 가진 연락처끼리 간선으로 연결한 뒤 DFS(깊이 우선 탐색)로 연결 요소를 찾는 방식으로 해결할 수 있습니다. 전체 흐름은 다음과 같습니다.

generate_graph() 함수를 정의합니다. 이 함수는 연락처 리스트(cnt), 연락처 개수(n), 인접 행렬(matrix)을 매개변수로 받습니다.
- i를 0부터 n-1까지, j를 0부터 n-1까지 반복하며 matrix[i][j] = 0으로 초기화합니다.
- 다시 i를 0부터 n-1까지, j를 i+1부터 n-1까지 반복하며 두 연락처의 세 슬롯(slot1, slot2, slot3)을 모두 교차 비교합니다. 하나라도 값이 일치하면 matrix[i][j]와 matrix[j][i]를 1로 설정하고 내부 루프를 종료합니다.
visit_using_dfs() 함수를 정의합니다. 현재 인덱스(i), 행렬(matrix), 방문 배열(visited), 결과 리스트(sol), 개수(n)를 받습니다.
- visited[i]를 True로 표시하고 i를 sol에 추가합니다.
- j를 0부터 n-1까지 순회하면서, 간선이 존재하고 아직 방문하지 않은 노드라면 재귀적으로 DFS를 수행합니다.
메인 함수(get_similar_contacts())에서는 다음 작업을 수행합니다.
- n := 연락처 개수, sol := 빈 리스트, matrix := n×n 행렬, visited := 길이 n의 배열(0으로 초기화)
- generate_graph(cnt, n, matrix)를 호출해 그래프를 생성합니다.
- 방문하지 않은 연락처마다 DFS를 실행하고, 그룹 구분을 위해 sol 끝에 -1을 추가합니다.
- 마지막으로 sol을 순회하며 값을 출력하되, -1을 만나면 줄을 바꿔 각 그룹을 구분해 보여줍니다.

구현 코드

아래는 위 접근 방식을 파이썬으로 구현한 전체 코드입니다.

class contact:
    def __init__(self, slot1, slot2, slot3):
        self.slot1 = slot1
        self.slot2 = slot2
        self.slot3 = slot3

def generate_graph(cnt, n, matrix):
    for i in range(n):
        for j in range(n):
            matrix[i][j] = 0
    for i in range(n):
        for j in range(i + 1, n):
            if (cnt[i].slot1 == cnt[j].slot1 or cnt[i].slot1 == cnt[j].slot2 or
                cnt[i].slot1 == cnt[j].slot3 or cnt[i].slot2 == cnt[j].slot1 or
                cnt[i].slot2 == cnt[j].slot2 or cnt[i].slot2 == cnt[j].slot3 or
                cnt[i].slot3 == cnt[j].slot1 or cnt[i].slot3 == cnt[j].slot2 or
                cnt[i].slot3 == cnt[j].slot3):
                matrix[i][j] = 1
                matrix[j][i] = 1
                break

def visit_using_dfs(i, matrix, visited, sol, n):
    visited[i] = True
    sol.append(i)
    for j in range(n):
        if (matrix[i][j] and not visited[j]):
            visit_using_dfs(j, matrix, visited, sol, n)

def get_similar_contacts(cnt):
    n = len(cnt)
    sol = []
    matrix = [[None] * n for i in range(n)]
    visited = [0] * n
    generate_graph(cnt, n, matrix)
    for i in range(n):
        if (not visited[i]):
            visit_using_dfs(i, matrix, visited, sol, n)
            sol.append(-1)
    for i in range(len(sol)):
        if (sol[i] == -1):
            print()
        else:
            print(sol[i], end=" ")

cnt = [contact("Amal", "amal@gmail.com", "+915264"),
    contact("Bimal", "bimal321@yahoo.com", "+1234567"),
    contact("Amal123", "+915264", "amal_new@gmail.com"),
    contact("AmalAnother", "+962547", "amal_new@gmail.com")]
get_similar_contacts(cnt)

실행 결과

0 2 3
1

동작 원리 정리

이 코드의 핵심은 다음과 같습니다.

그래프 생성: 모든 연락처 쌍을 비교하여 세 개의 슬롯 중 하나라도 일치하면 양방향 간선을 만듭니다. 이렇게 하면 필드 순서가 달라도 동일한 사람임을 판별할 수 있습니다.
연결 요소 탐색: DFS를 통해 서로 연결된 연락처들을 한 그룹으로 묶습니다. 방문 배열 덕분에 이미 처리된 연락처는 건너뛰게 됩니다.
그룹 구분 출력: 각 DFS 탐색이 끝날 때 -1을 삽입하여, 출력 시 그룹 사이에 줄바꿈이 발생하도록 합니다.