문제 소개
연락처 목록에 여러 사람의 메일 ID가 담겨 있다고 가정해 보겠습니다. 각 행(연락처)에는 동일한 사람의 메일 ID가 두 개 이상 포함될 수 있습니다. 어떤 연락처 i에 대해, j < i를 만족하는 j가 존재하고 연락처 j가 연락처 i와 하나 이상의 공통 이메일을 공유한다면, 연락처 i는 중복으로 간주합니다. 우리의 목표는 연락처 목록에서 고유한 사람의 수를 구하는 것입니다.
예를 들어 입력이 다음과 같다고 해보죠.
contacts = [["alex@gmail.com", "alex@yahoo.com"], ["alex_25@yahoo.com", "alex@gmail.com"], ["bob15@gmail.com"]]
첫 번째 연락처와 두 번째 연락처는 alex@gmail.com이라는 동일한 이메일을 공유하므로 같은 사람입니다. 따라서 이 경우 출력은 2가 됩니다.
풀이 접근 방법
이 문제는 집합(set) 자료구조를 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 지금까지 등장한 모든 이메일을 집합에 기록해 두고, 새로운 연락처의 이메일이 이미 집합에 존재하는지 확인하는 것입니다. 단계별로 정리하면 다음과 같습니다.
- ans := 0 (고유한 사람 수)
- found := 빈 집합 (지금까지 발견한 이메일 저장)
- contacts의 각 연락처 c에 대해:
- duplicate := False
- c의 각 email에 대해:
- email이 found에 없으면, found에 추가
- 그렇지 않으면, duplicate := True
- duplicate가 False이면, ans := ans + 1
- ans 반환
즉, 한 연락처의 이메일이 하나라도 이전에 등장한 적이 있다면 그 연락처는 이미 카운트된 사람의 것이므로 세지 않습니다. 반대로 완전히 새로운 이메일만 담고 있는 연락처라면 새로운 사람으로 간주하여 카운트를 1 증가시킵니다.
예제 코드
다음은 위 알고리즘을 Python으로 구현한 예제입니다. 더 나은 이해를 위해 직접 실행해 보세요.
def solve(contacts):
ans = 0
found = set()
for c in contacts:
duplicate = False
for email in c:
if email not in found:
found.add(email)
else:
duplicate = True
if not duplicate:
ans += 1
return ans
contacts = [
["alex@gmail.com", "alex@yahoo.com"],
["alex_25@yahoo.com", "alex@gmail.com"],
["bob15@gmail.com"]
]
print(solve(contacts))
입력
[["alex@gmail.com", "alex@yahoo.com"], ["alex_25@yahoo.com", "alex@gmail.com"], ["bob15@gmail.com"] ]
출력
2
복잡도 분석
전체 이메일 개수를 N이라고 할 때, 모든 이메일을 한 번씩 순회하며 집합에서 O(1) 평균 시간에 조회·삽입하므로 시간 복잡도는 O(N)입니다. 공간 복잡도 역시 발견한 이메일을 모두 저장하는 집합 때문에 O(N)입니다. 덕분에 연락처 데이터가 커져도 효율적으로 처리할 수 있습니다.