BoJ 4158 - CD [with python]

📍 문제

문제

상근이와 선영이는 동시에 가지고 있는 CD를 팔려고 한다. CD를 몇 개나 팔 수 있을까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄부터 N개 줄에는 상근이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. 다음 M개 줄에는 선영이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. CD의 번호는 십억을 넘지 않는 양의 정수이다. 입력의 마지막 줄에는 0 0이 주어진다.

상근이와 선영이가 같은 CD를 여러장 가지고 있는 경우는 없다.

예제 입력

3 3
1
2
3
1
2
4
0 0

예제 출력

2

📍 아이디어

이분 탐색으로 풀다가 계속 시간 초과가 떠서 문제를 자세히 읽어보니 상근이와 선영이가 같은 CD를 여러장 가지고 있는 경우는 없다. 라는 문구가 있었다.
따라서 리스트 보다 시간 복잡도가 더 낮은 자료 구조인 set 을 사용하여 문제를 풀었고,
set의 경우 겹치는 부분(=교집합)을 구할 수 있는 intersection이 있어 그 교집합의 길이를 출력해주었다~

📎 풀이

import sys

while True:
    n, m = map(int, sys.stdin.readline().rstrip().split(" "))

    if n == m == 0:
        break

    sg = set(int(sys.stdin.readline().rstrip()) for _ in range(n))
    sy = set(int(sys.stdin.readline().rstrip()) for _ in range(m))

    res = len(sg.intersection(sy))
    print(res)