[python_파이썬_Pass]백준_2776번_암기왕_이분탐색_풀이

공부하는허딩크 : https://www.youtube.com/live/LeGt8NxRPdY?feature=shared

- YouTube

 

<첫번째 시도 : 맞았습니다>

유사한 문제를 먼저 풀어서 동일한 방법으로 바로 해결했다.

딕셔너리를 만들어 주고 get함수를 이용하면 쉽게 해결 할 수 있다. (활용방법은 아래 참고)

백준 수찾기_1920번: https://heodinkcodingdiary.tistory.com/104

[python_파이썬_Pass]백준_1920번_수찾기_이분탐색_풀이

import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):

    N = int(input())

    note1 = list(map(int, input().split()))

    M = int(input())

    note2 = list(map(int, input().split()))

    dict = {}

    for i in note1:

        dict[i] = 1

    for i in note2:

        print(dict.get(i, 0))

 

<다른 사람풀이 참고>

이거 충격이었다. set함수를 이용해서 찾는 모수의 요소들을 set으로 묶어주면 시간초과가 통과된다.

#set사용

T = int(input())

for _ in range(T):

    N = int(input())

    note1 = set(map(int, input().split()))

    M = int(input())

    note2 = list(map(int, input().split()))

    for i in note2:

        if i in note1:

            print(1)

        else:

            print(0)

 

<추가 풀이 : 맞았습니다.>

이진탐색을 활용해서 해결했다. sort가 중요하다.

import sys

input = sys.stdin.readline

T = int(input())

#Binary_Search

def BS(arr, m):

    start, end = 0, len(arr) - 1

   

    while start <= end:

        mid = (start + end) // 2

        if arr[mid] == m:

            return True

        elif arr[mid] > m:

            end = mid - 1

        else:

            start = mid + 1

    return False

       

for _ in range(T):

    N = int(input())

    note1 = list(map(int, input().split()))

    M = int(input())

    note2 = list(map(int, input().split()))

    note1.sort()

   

    for i in note2:

        if BS(note1, i):

            print(1)

        else:

            print(0)

 

이진탐색 재귀함수를 활용했다. 이제는 조금 감이 잡힌다.

import sys

input = sys.stdin.readline

T = int(input())

#Binary_Search_재귀함수 활용

def BS(target, start, end):

    if start > end:

        return 0

   

    mid = (start + end) // 2

    if note1[mid] == target:

        return 1

    elif note1[mid] > target:

        end = mid - 1

    else:

        start = mid + 1

   

    return BS(target, start, end)

   

   

for _ in range(T):

    N = int(input())

    note1 = list(map(int, input().split()))

    M = int(input())

    note2 = list(map(int, input().split()))

    note1.sort()

   

    for i in note2:

        print(BS(i, 0, N - 1))