👩‍💻🔠 [baekjoon] 1764번: 듣보잡

🖍️ solution 1

import sys
"""
[풀이 시간]
1) 15:50 ~ 16:10

[요약]
1) 명단 A, 명단 B의 교집합 구하는 문제

[전략]
1) 두 명단을 세트 자료형에 넣고 교집합을 구해주기
"""
N, M = map(int, sys.stdin.readline().split())
set_a, set_b = set(), set()

# 듣도 못한 사람 명단
for _ in range(N):
    set_a.add(sys.stdin.readline().rstrip())

# 보도 못한 사람 명단
for _ in range(M):
    set_b.add(sys.stdin.readline().rstrip())

result_list = sorted(list(set_a & set_b))
print(len(result_list))
for name in result_list:
    print(name)

💡 idea 1

• 1) 두 명단을 개별 세트 자료형에 넣고 교집합 확인

🖍️ solution 2

import sys

"""
[풀이 시간]
1) 15:50 ~ 16:10

[요약]
1) 명단 A, 명단 B의 교집합 구하는 문제

[전략]
1) 명단 A의 애들을 전부 사전에 넣어 주자
"""
N, M = map(int, sys.stdin.readline().split())
result_list, name_dict = [], {}

# 듣도 못한 사람 명단
for _ in range(N):
    name_dict[sys.stdin.readline().rstrip()] = True

# 보도 못한 사람 명단
for _ in range(M):
    tmp_name = sys.stdin.readline().rstrip()
    try:
        if name_dict[tmp_name]:
            result_list.append(tmp_name)
    except KeyError as e:
        pass

result_list.sort()
print(len(result_list))
for name in result_list:
    print(name)

💡 idea 2

• 1) 한쪽 명단을 모두 사전에 넣기
  • 사전의 value는 True로 모두 초기화
• 2) 다음 명단의 개별 사람들을 이미 사전에 있는지 대조
  • 예외 처리 구문을 이용, 사전에 이미 등재된 사람이라면 결과 리스트에 추가

😇 Comparison

결과 비교

제일 상단의 제출 결과가 solution 1, 하단의 결과가 solution 2에 해당 된다. 시간 복잡도는 전자가, 공간 복잡도는 후자가 더 효율적인 것으로 나타난다.