[백준 1920] 수찾기 / 파이썬 + 이분 탐색

정수 A[1], A[2],...,A[N]이 주어져있을 때 이 안에 X라는 정수가 존재하는지 확인하는 프로그램을 짜는 문제이다.

일단 하던 대로 짜보았다.

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))
M = int(input())
for n in list(map(int, input().split())):
    if n in nums:
        print("1")
    else:
        print("0")

엥 시간초과가 뜬다.
찾기 == 탐색 이니까 알고리즘 문제인가?
분류를 보니 이분탐색이라고 떡하니 적혀있다.

이분탐색 정도는 뭐 C언어 수업에서 배웠다. 그래도 정리하고 가자

이분탐색(binary search)이란?

• 이진탐색 또는 이분탐색이라 불리는 알고리즘은 정렬된 리스트에서 탐색 범위를 절반씩 삭제하면서 데이터를 탐색하는 것이다.
• start, mid, end를 사용해서 탐색하고, 찾고자하는 데이터와 중간 위치의 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.
• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.

코드로 구현해보자.
1. 우선, 정렬이 되어있어야 이분탐색을 하기 편하니, N개의 정수는 리스트로 받아 정렬시킨다. M개의 수는 예제 출력과 순서를 동일하게 맞추기 위해 리스트로 받는다.
2. 이분탐색 구현 (bisect라는 라이브러리도 존재한다.)
-> 반복문으로 구현할 수도 있고, 반복적인 작업을 하므로 재귀함수로 구현해도 되겠다.

❗ 정렬 시 nums = list(map(int, input().split())).sort() 처럼 리스트를 sort한 것을 변수에 집어넣으면 None이 변수에 담기게 된다. 정렬한 것을 변수에 저장할 때는 nums = sorted(list(map(int, input().split()))) 로 쓰는게 낫다.

def BinarySearch(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if arr[mid] == target:
            return '1'
        elif arr[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return '0'

N = int(input())
nums = sorted(list(map(int, input().split())))
M = int(input())
target = list(map(int, input().split()))

for x in target:
    print(BinarySearch(nums, x, 0, N - 1))

재귀함수로 나타낼 수도 있다.

def BinarySearch(arr, target, start, end):
    if start > end:
        return '0'
    mid = (start + end) // 2
    if arr[mid] == target:
        return '1'
    elif arr[mid] < target:
        return BinarySearch(nums, target, mid + 1, end)
    else:
        return BinarySearch(nums, target, start, mid - 1)

N = int(input())
nums = sorted(list(map(int, input().split())))
M = int(input())
target = list(map(int, input().split()))

for x in target:
    print(BinarySearch(nums, x, 0, N - 1))

풀고 나서 다른 사람들의 풀이도 보니, 이진탐색 없이도 풀리나 보다.

import sys
input = sys.stdin.readline

N = input()
nums = set(map(int, input().split()))
M = input()
target = list(map(int, input().split()))

for x in target:
    print(1 if target in nums else 0)