백준 : 4158번 CD [파이썬, 실버5, 이분탐색]

문제

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

입력

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

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

출력

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

예제 입력 1 복사

3 3
1
2
3
1
2
4
0 0

예제 출력 1 복사

2

[문제풀이]

* 다음과 같은 입력이 주어졌을 경우

1 2 4 10

1 4 10 13

우선 index가 0인 지점부터 상근이와 선영이를 비교한다.

 

1 2 4 10

1 4 10 13

 

같은 번호를 가졌으니 카운트는 하나 올라가게 된다.

그리고 두 번호는 더이상 비교할 필요가 없으니 모두 인덱스를 하나 증가시킨다.

 

1 2 4 10

1 4 10 13

다음 인덱스에서 서로 번호가 같지 않다.

그렇다면, 이전처럼 상근이와 선영이의 인덱스 모두를 증가시키면 안된다.

증가시킨다면, 번호가 4인 경우를 찾지 못하게 된다.

 

여기서 오름차순으로 주어진 것을 활용할 수 있다.

비교한 두 수에서 작은 수를 가진 사람의 인덱스를 증가시키는 것이다.

작은 수를 가진 사람이 다음 수들 중 현재 비교 대상이 있을 수 있기 때문이다.

그리고 둘 배열 중 하나라도 끝지점에 도달하면 더이상 비교할 필요가 없다.

 

import sys

while True:
    a,b = map(int, sys.stdin.readline().split())
    if a==0 and b==0:
        break
    ary1 = [int(sys.stdin.readline()) for _ in range(a)]
    ary2 = [int(sys.stdin.readline()) for _ in range(b)]
    ans = 0
    
    for cd in ary2:
        start, end = 0, a-1
        while start <= end:
            mid = (start+end)//2
            
            if ary1[mid]==cd:
                ans+=1
                break
            elif ary1[mid]>cd:
                end = mid -1
            elif ary1[mid]<cd:
                start=mid+1
    print(ans)

정답코드

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을 통해 입력을 받았다.