[BOJ] 1920. 수 찾기

Python3

문제

https://www.acmicpc.net/problem/1920

키워드

• 이분탐색 (시간복잡도 O(logN))

문제 풀이

문제 요구사항

• N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램
• 존재하면 1을, 존재하지 않으면 0을 출력

변수 및 함수 설명

• N : (1 ≤ N ≤ 100,000)
• arr : N개의 정수 (A[1], A[2], …, A[N]) 가 들어 있는 배열
• M : (1 ≤ M ≤ 100,000)
• chk : M개의 수, 이 수들이 A안에 존재하는지 체크하는 배열
  모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.
• first : 리스트의 첫 번째 값
• last : 리스트의 마지막 값
• mid : 리스트의 중간 값
• value : 리스트에 존재하는지 확인하는 타겟 값

• binary_search(value) : 이진 탐색을 수행하는 함수

풀이

(입력 및 선언)

• n과 n개의 정수(arr), m과 m개의 정수(chk)를 입력 받는다.
• 탐색 리스트인 arr는 정렬해야 한다.
  이분 탐색을 수행하기 위해서는 주어진 탐색 리스트가 이미 정렬되어 있다는 전제가 깔려야 하기 때문이다.

(binary_search 함수)

• 리스트의 첫 번째 값인 first, 리스트의 마지막 값인 last, 리스트의 중간 값인 mid를 선언한다.
• 이때 mid 값은 first와 last가 이동하면서 자연스레 값이 달라질 것이다. mid 값은 first보다 크고, last보다는 작은 중간에 위치하기 때문에 while 문 밖이 아니라 안에 넣어줘야 한다. (아니면 오류남)
• first와 last가 만나게 되거나 first가 last보다 앞질러서 커지기 전까지 반복한다.
• 만약 리스트의 중간 값이 찾는 value와 같다면, 존재하는 값이므로 True를 반환한다.
• 만약 mid가 가리키는 값이 찾는 수(value)보다 크다면, last를 (mid-1)한 만큼 줄인다.
• 만약 mid가 가리키는 값이 찾는 수(value)보다 작다면, first를 (mid+1)한 만큼 늘린다.
  
  출처: https://daebaq27.tistory.com/37

(최종 출력)

• 체크할 배열(chk)을 돌면서 arr에 존재하는지 판단한다
• binary_search 함수를 호출했을 때 True가 반환되면 1을 출력하고, 그렇지 않으면 0을 출력한다.

최종 코드

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
m = int(input())
chk = list(map(int, input().split()))

def binary_search(value) :
    first, last = 0, n-1
    
    while first <= last :
        mid = (first + last) // 2
        
        if arr[mid] == value :
            return True
        if arr[mid] > value :
            last = mid - 1
        else :
            first = mid + 1
            
for i in chk :
    if binary_search(i) :
        print(1)
    else : print(0)