백준 알고리즘 1764번 듣보잡(python)

집합을 사용한 방식

합집합을 사용하면 쉽게 풀 수 있다.

a, b = map(int, input().split())
s1, s2 = set(), set()
for _ in range(a):
    s1.add(input())
for _ in range(b):
    s2.add(input())
li = sorted(s1 & s2)

print(len(li))
for s in li:
    print(s)

 

이분 탐색을 사용한 방식

1) 집합을 사용한 방식과 속도가 비슷하다. input함수를 사용해서 입력을 읽는 게 시간이 오래 걸리는 것 같다.

def binarySearch(li, n):
    s, e = 0, len(li)-1
    while s <= e:
        m = (s + e) // 2 
        if li[m] == n:
            return 1
        if n > li[m]:
            s = m + 1
        else:
            e = m - 1
    return 0
    
    
a, b = map(int, input().split())
result = []
li1 = sorted([input() for _ in range(a)])
li2 = sorted([input() for _ in range(b)])
for s in li2:
    if binarySearch(li1, s):
        result.append(s)

print(len(result))
for c in sorted(result):
    print(c)

2) stdin.readline을 사용해서 해결했다. 이 방법이 훨씬 빠르다.

readline() 뒤에 rstrip을 사용하지 않으면 출력 형식이 잘못되었습니다 라는 결과가 나온다.

뒤의 공백이 출력되면 안 되는 것 같다.

from sys import stdin

a, b = map(int, input().split())
result = []
li1 = sorted([stdin.readline().rstrip() for _ in range(a)])
li2 = sorted([stdin.readline().rstrip() for _ in range(b)])
for s in li2:
    if binarySearch(li1, s):
        result.append(s)

print(len(result))
for c in sorted(result):
    print(c)

input -> 3784s, stdin.readline -> 280ms