[백준 BOJ / Python] 4158번 CD

문제

상근이와 선영이가 동시에 갖고 있는 cd의 개수를 구하면 되는 문제이다.
다만 주의할 점은 여러 개의 테스트 케이스로 이루어져 있다는 점이다.
예제는 한 개만 나와 있어 헷갈릴 수 있어 조심해야한다.

풀이

• 이 문제는 자료구조로 접근하면 쉽다.
• 중복되는 cd 번호가 없기 때문에 set 집합 자료구조를 사용하면 된다.
  즉, 상근이의 cd 집합과 선영이의 cd 집합의 교집합 개수를 구하면 된다.
• 집합에 담을 땐 add 함수를 통해 넣고, 
  교집합(&)은 set(a) & set(b)와 같은 방법으로 구할 수 있다.
• 혹은 교집합을 구하는 대신 상근이의 cd 집합에 선영이가 가진 cd가 포함되는지 셈을 통해 구할 수도 있다.
  set 집합의 경우에는 탐색 시간이 O(1)이기 때문에 속도도 조금 더 빠르고,
  선영이의 cd 집합 정보를 따로 저장하지 않고 비교함으로 더 적은 메모리가 사용된다.

Python 코드

# 입출력 속도를 빠르게 함
import sys
input = sys.stdin.readline
print = sys.stdout.write

# 교집합을 사용하여 구하는 법
res = []
while True:
    n, m = map(int, input().split())
    if n == m == 0: # n과 m 모두 0이면 종료
        break
    sang = set([int(input()) for _ in range(n)])
    sun = set([int(input()) for _ in range(m)])
    res.append(str(len(sang&sun)))
    
print("\n".join(res)) # 한번에 출력


# 집합 요소와 비교하여 구하는 법
res = []
while True:
    n, m = map(int, input().split())
    if n == m == 0: # n과 m 모두 0이면 종료
        break
    sang = set([int(input()) for _ in range(n)])
    ans = 0
    for _ in range(m):
    	# 선영이 cd 번호를 바로 받으며 확인
        if int(input()) in sang:
            ans += 1
    res.append(str(ans))
    
print("\n".join(res)) # 한번에 출력

 

문제출처

4158번: CD