[Python] 파이썬 백준(1920) 수 찾기

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

1920번: 수 찾기

---

https://pasongsong.tistory.com/204?category=1026284 

[알고리즘] 이진 탐색 Binary Search

---

나의 풀이

반복문을 돌려 풀면되는 간단한 문제이지만 그렇게 풀면 시간초과된다.

• Binary Search를 사용함

from sys import stdin, stdout

cnt_num1 = stdin.readline()
num_list = sorted(map(int,stdin.readline().split()))

cnt_num2 = stdin.readline()
find_list = map(int, stdin.readline().split())


def search_num(num_list, find_num):
    len_list = len(num_list)//2


    if num_list[len_list] == find_num:
        return 1
    elif len(num_list) == 1:
        return 0
    elif num_list[len_list] > find_num:
        return search_num(num_list[:len_list], find_num)
    elif num_list[len_list] < find_num:
        return search_num(num_list[len_list:], find_num)

    return 0

for i in find_list:
    print(search_num(num_list, i))

처음 코드였는데 시간 초과가 나서 다른 블로그를 참고해보니

len_list = len(num_list)//2

이 부분이 문제였던 것 같다. input값으로 썼던 cnt2_num을 사용해야겠음

---

나의 풀이 2

• Binary Search를 사용하였고 len() 때문에 시간 초과가 나는 거 같아 input 값으로 받았던 길이 값을 사용하여 코드 수정

from sys import stdin, stdout

cnt_num1 = int(stdin.readline())
num_list = sorted(map(int,stdin.readline().split()))

cnt_num2 = stdin.readline()
find_list = map(int, stdin.readline().split())



def search_num(num_list, find_num, start, end):
    median_num = (start + end) //2

    if start >= end:
        return 0
    elif num_list[median_num] < find_num:
        return search_num(num_list, find_num, median_num+1, end)

    elif num_list[median_num] > find_num:
        return search_num(num_list, find_num, start, median_num)
    else:
        return 1


for i in find_list:
    print(search_num(num_list, i, 0, cnt_num1))