[이분탐색/백준] 1920번 : 수 찾기

- 문제 : https://www.acmicpc.net/problem/1920

 

Silver4 문제이고, 스스로 푼 문제다!

전형적인 이분탐색 문제였기에 그렇게 어렵지는 않았다. 

다만 mid를 설정할 때 left + right + 1을 2로 나눈 몫으로 해야하는 걸 까먹어서 약간 헤맸다. 

 

- 정답 풀이1 : 

이분 탐색으로 푸는게 확실히 이중 탐색보다 5배 정도 시간이 빠른 것 같다. 

import sys
input = sys.stdin.readline

n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))
arr1.sort()

#arr2에 있는 원소들이 arr1에 있는지 여부 확인
answer = [0] * m
for i in range(m):
    if answer[i] == 1:
        continue
        
    left, right = 0, n - 1
    target = arr2[i]
    while left <= right:
        mid = (left + right + 1) // 2
        if arr1[mid] == target:
            answer[i] = 1
            break
        if target < arr1[mid]:
            right = mid - 1
        else:
            left = mid + 1
            
            
for i in range(m):
    print(answer[i])

 

- 정답 풀이2 : 

문제 보자마자 작성한 코드. 이렇게 하면 Python으로 돌렸을 때 10%에서 시간초과가 나고, Pypy3으로 돌리면 좀 오래 걸리지만 통과한다. 

n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))
arr1.sort()

#arr2에 있는 원소들이 arr1에 있는지 여부 확인
answer = [0] * m
for i in range(m):
    if arr2[i] in arr1:
        answer[i] = 1

for i in range(m):
    print(answer[i])