[코딩테스트 연습(Python)] 백준 1920번_수 찾기(이진 탐색)

 

얼핏 보기엔 매우 간단한 A리스트에서 M리스트의 값을 찾는 문제이지만 시간 제한에 함정이 있다.

처음엔 in으로 쉽게 풀어보려 했지만 시간 초과가 났다.

 

검색해보니 본 문제는 '이진 탐색' 알고리즘을 적용하여 풀어야 하는 문제였다. (in으로 풀지 못하는 건 아니다)

 

in, 이진 탐색 두 가지 풀이로 풀어보았다.

 

1. in을 사용한 풀이

import sys
input = sys.stdin.readline

N = int(input())
# set으로 미리 중복을 제거해주지 않으면 시간 초과
N_list = set(list(map(int, input().split())))

M = int(input())
M_list = list(map(int, input().split()))

for i in M_list:
    if(i in N_list):
        print(1)
    else:
        print(0)

 

2. 이진 탐색(binary search)을 사용한 풀이

import sys
input = sys.stdin.readline

N = int(input())
N_list = list(map(int, input().split()))
# 이진 탐색을 위해 N배열을 미리 정렬
N_list.sort()

M = int(input())
M_list = list(map(int, input().split()))

def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        # target이 중앙값일 경우
        if data[mid] == target:
            return 1
        # target이 중앙값보다 클 경우 
        # 중앙값을 포함한 왼쪽 index들은 볼 필요가 없다.
        elif data[mid] > target:
            end = mid -1
        # target이 중앙값보다 작을 경우 
        # 중앙값을 포함한 오른쪽 index들은 볼 필요가 없다.
        else:
            start = mid + 1
    return 0

for i in M_list:
    if binary_search(i, N_list):
        print(1)
    else:
        print(0)