[백준-python]1764 듣보잡

문제 낸 사람이 누군짘ㅋㅋㅋㅋ 엄청 웃으면서 푼 문제다.

알고리즘 분류

• 이진 탐색
• 문자열
• 정렬

첫 번째 시도

당연히 시간초과 났다.

#coding:utf8
# 듣보잡
# 이진탐색

from sys import stdin
N, M = map(int, stdin.readline().split())
NList = [stdin.readline().rstrip() for i in range(N)]      # 듣도 못한 사람 리스트
MList = [stdin.readline().rstrip() for j in range(M)]    # 보도 못한 사람 리스트
idiots = list()

for m in MList:
    for n in NList:
        if n in MList:
            if n not in idiots:
                idiots.append(n)

idiots.sort()
print(len(idiots))
for dumb in idiots:
    print(dumb)

최종 정답

알고보니 문자열끼리도 비교연산자로 비교가 가능했다. 숫자 이진탐색이랑 똑같이 풀면 된다.
python3으로 처음 제출해봤는데 확실히 빠른듯

#coding:utf8
# 듣보잡
# 이진탐색

from sys import stdin
N, M = map(int, stdin.readline().split())
NList = sorted([stdin.readline().rstrip() for i in range(N)])      # 듣도 못한 사람 리스트
MList = sorted([stdin.readline().rstrip() for j in range(M)])    # 보도 못한 사람 리스트

def binary_search(searchList, target, startIndex, endIndex):
    if startIndex > endIndex:
        return False

    mid = (startIndex+endIndex) // 2
    if target == searchList[mid]:
        return True
    if target > searchList[mid]:
        return binary_search(searchList, target, mid+1,endIndex)
    else:
        return binary_search(searchList, target, startIndex, mid-1)

count = 0
idiots = list()
for m in MList:
    startIndex = 0
    endIndex = N-1
    if binary_search(NList, m, startIndex, endIndex):
        count += 1
        idiots.append(m)

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

Referece

https://comdoc.tistory.com/entry/32-%EC%9D%B4%EC%A7%84-%EA%B2%80%EC%83%89Binary-Search