(Python) - BOJ(1920번) : 수 찾기

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

1920번: 수 찾기

---

• 해설 : 

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 문제이다.

 

 

 

---

• 풀이 :

A배열 안에 숫자가 들어있는지 찾는 문제이다. 배열의 길이와 찾는 숫자의 길이가 최대 100,000이므로 O(N^2)인

모든 원소에 대해 if X in A: 를 사용하면 안된다. 따라서 이분탐색으로 해당 원소가 배열 안에 있는지 찾도록 구현하였다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
if __name__ == "__main__":
    N = int(input())
    A = sorted(list(map(int,input().split())))
    M = int(input())
    B = list(map(int,input().split()))
    for i in B:
        start = 0
        end = N-1
        flag = False
        while start <= end:
            mid = (start + end) // 2
            if A[mid] < i:
                start = mid + 1
            elif A[mid] > i:
                end = mid - 1
            else:
                flag = True
                print(1)
                break
        if not flag:
            print(0)