백준 4158번 파이썬

문제 링크

https://www.acmicpc.net/problem/4158

4158번: CD

 

시간 제한 / 메모리 제한

1 초

256 MB

 

문제

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

 

입력

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

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

출력

두 사람이 동시에 가지고 있는 CD의 개수를 출력한다.

예제 입력

3 3
1
2
3
1
2
4
0 0

예제 출력

2

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

while True:
    cd = defaultdict(bool)
    n, m = map(int, input().split())
    cnt = 0
    if n == 0 and m == 0:
        break
    for _ in range(n):
        cd[int(input())] = True
    for _ in range(m):
        if cd[int(input())]:
            cnt += 1

    print(cnt)

 

defaultdict(bool) 을 활용해 상근이가 갖고 있는 CD(key)를 True(value)로 설정했다. 그리고 선영이가 갖고 있는 CD마다 dictionary[선영CD]의 bool 값을 확인하여 True면 cnt += 1 하여 팔 수 있는 CD 수를 측정했다. 또한 입력값이 최대 200만(N <= 10^6,  M<= 10^6)이 넘기에 시간 초과를 방지하고자 더 빠른 입력인 sys.stdin.readline을 통해 입력을 받았다.

 

 

 

참고자료

https://docs.python.org/3/library/collections.html#collections.defaultdict

collections — Container datatypes — Python 3.10.4 documentation