[백준]1920번:수 찾기 (python 파이썬)

문제

www.acmicpc.net/problem/1920

1920번: 수 찾기

풀이

일반 반복문으로 풀게되면 시간초과가 뜬다.

이분법을 사용하여 풀어야한다.

 

A = [ 4, 1, 5, 2, 3 ]

B = [ 1, 3, 7, 9, 5 ]

 

주어졌을 때, A를 오름차순으로 정렬시킨다.

 

A = [ 1, 2, 3, 4, 5 ]

B = [ 1, 3, 7, 9, 5 ]

 

A의 첫번째 인덱스를 start에 넣고, 마지막 인덱스를 end 에 넣은 후 시작.

B[0]부터 확인한다고 하자(B[0]=1)

m = (start+end)/2 값을 넣고,

[ 1, 2, 3, 4, 5 ]

  s     m    e

start > end 면 return 0

B[0] == A[m] 이면, return 1

B[0] < A[m] 이면 end = m-1로 다시 함수 호출

B[0] > A[m] 이면 start = m+1로 다시 함수 호출

 

소스코드

def find_num(i, start, end):
    if start>end:
        return 0
    m = (start+end)//2
    if i == a[m]:
        return 1
    elif i > a[m]:
        return find_num(i, m+1, end)
    else:
        return find_num(i, start, m-1)

n = int(input())
a = list((map(int, input().split())))
a.sort()

m = int(input())
b = list(map(int, input().split()))

for i in b:
    start = 0
    end = n-1
    print(find_num(i, start, end))