백준 1920 - 수 찾기

처음 별 생각없이 했다가 시간 초과와 맞딱뜨렸다

 

def bk1920_find_number():
    # n
    # n 개의 정수
    # m
    # m 개의 정수
    # m리스트의 숫자가 m에 있는지 없는지 체크하면 됨
 
    n = int(input())
    n_list = list(input().split(" "))
 
    m = int(input())
    m_list = list(input().split(" "))
 
    for i in m_list:
        try :
            test = n_list.index(i)
            print(1)
        except :
            print(0)
            
bk1920_find_number()

 

힝 ... 그래서 이진탐색을 사용해보기로 함.

근데 문제는 ... 이진탐색 개념으로는 알고 있는데 이거 코드로 구현하려니 갑자기 막막해짐.

근데 이진탐색이랑 이분탐색이랑 차이가 뭐임? 같은? 단어인듯 ? ?

 

이진탐색을 구현하면서 배운 것 : 가장 낮은 수와 가장 높은수를 더한 후 나누기 2를 하면 가운데 수를 구할 수 있다.

이거 진짜 중요한듯... 수학적인 부분이 전무하다시피 하니까 이런 사소한데서 정말 골치가 많음 8_8

 

def bk1920_find_number():
    # n / n 개의 정수
    # m / m 개의 정수
    # m 리스트의 숫자가 m에 있는지 없는지 체크하면 됨
    # 전부 탐색하면 시간이 미쳐돌아가기 때문에 이분탐색을 사용하기
 
    n = int(input())
    n_list = list(input().split(" "))
    n_list.sort()
 
    m = int(input())
    m_list = list(input().split(" "))
 
    # m 리스트 첫번째 값이 n 리스트에 있는지 확인하기
    for i in m_list:
        bottom = 0
        top = n - 1
        result = 0
        while bottom <= top :
            middle = ( top + bottom ) // 2
            if i == n_list[middle] :
                result = 1
                break
            elif i > n_list[middle] :
                # 중간값보다 한칸 오른쪽으로 이동해야 하기 때문에 플러스!
                bottom = middle + 1
            else :
                # 중간값보다 한 칸 왼쪽으로 이동해야 하기 때문에 마이너스!
                top = middle - 1
        print(result)
 
bk1920_find_number()

 

어쨌든 해냈다. . . 이진탐색 할 때 이미지로 상상하는게 좋은 것 같아.