[파이썬] 1764. 듣보잡

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

 

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

예제 입력 1

3 4

ohhenrie

charlie

baesangwook

obama

baesangwook

ohhenrie

clinton

예제 출력 1

2

baesangwook

ohhenrie

 

 

💗 나의 풀이

 

N, M=map(int, input().split())
unhear=set()
unseen=set()
for i in range(N):    # 듣도 못한 사람의 수
    unhear.add(input())
for j in range(M) :   # 보도 못한 사람의 수
    unseen.add(input())

ans=sorted(unhear&unseen)
print(len(ans))
print('\n'.join(ans))

 

set의 교집합을 사용해서 풀었다.

join으로 줄바꿈하면서 문자열로 출력한다.

 

 

💜 다른 사람 풀이

 

n, m=map(int, input().split())

a=[]
b=[]

for _ in range(n) :
    a.append(input())

for _ in range(m) :
    b.append(input())

c=sorted(list(set(a)&set(b)))

print(len(c))
for item in c :
    print(item)

 

입력 받은 문자열을 리스트에 추가한다.

교집합을 만든 후 다시 리스트로 만들고 정렬한다. 

반복문을 사용하여 결과를 출력한다.

 

 

from sys import stdin

n, m=map(int, stdin.readline().split())
nList=sorted([stdin.readline().rstrip() for _ in range(n)])
mList=sorted([stdin.readline().rstrip() for _ in range(m)])

idiots=list()
def binSearch(target) :
    left=0
    right=len(nList)-1
    while left <= right :
        mid=(right+left)//2
        if target == nList[mid] :
            idiots.append(target)
            break
        elif target > nList[mid] :
            left=mid+1
        else :
            right=mid-1

for target in mList :
    binSearch(target)

print(len(idiots))
for i in idiots :
    print(i)

 

이진 탐색을 사용해서 효율이 좋다.

이분법이랑 이진 탐색이랑 같은 말인줄 알았는데 아니다. 이분법은 수학에서 근을 찾는 방법이다.

두 명단은 입력 받고 나서 바로 오름차순 정렬한다.

left가 right보다 더 커질 때까지 반복한다.

두 명단에서 서로 중복되는 것은 리스트에 담는다.

 

 

문제 출처 💁‍♀️ 백준