[알고리즘] 백준 2776 파이썬 - 암기왕

2776번: 암기왕

 

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

​

문제풀이

import sys
input =sys.stdin.readline

#01
def search(s,e,num1,num):
    while s<=e:
        mid=(s+e)//2
        if num1[mid]==num:
            return 1
        elif num1[mid]<num:
            s=mid+1
        else:
            e=mid-1
    return 0

n=int(input())

for _ in range(n):
    #02
    x=int(input())
    a=list(map(int,input().split()))
    a.sort()
    #03
    y=int(input())
    b=list(map(int,input().split()))
    for num in b:
        print(search(0,x-1,a,num))

 

- #01 : 이진탐색을 사용해서 시간초과가 걸리지 않게 해준다.

- #02 : 원본 값을 a에 리스트형태로 int형으로 저장한다. a는 이진탐색을 위해 오름차순 정렬한다.

- #03 : b에 원본 값과 비교할 데이터를 저장한다.

for문을 이용해 b의 값을 하나씩 num에 저장하여

해당값이 원본 리스트에 있는지 이진탐색을 이용해서 확인한다.