수 찾기_1920

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

문제 접근법

이 문제의 의도는 이분탐색을 통해 푸는 것이다. 처음에 제한시간을 고려하지 않고 풀다가 시간초과가 난 방법부터 소개하도록 하겠다.

for문을 이용해 배열의 각 요소가 또 다른 배열 안에 있는지 탐색하면 된다.

1. input입력받기

import sys
input = sys.stdin.readline

n = int(input())
arr_n = list(map(int, input().split()))
m = int(input())
arr_m = list(map(int, input().split()))

2. 탐색

for _ in arr_m:
     print(1) if _ in arr_n else print(0)

3. 결과
   

시간복잡도가 O(N^2)으로 높아 시간초과가 발생한 것으로 보인다.

이에 정렬 후 분할 탐색하는 이진탐색의 방법을 사용하면 시간복잡도는 O(NlogN)으로 줄어들어 시간초과 발생을 막을 수 있지 않을까?

이진탐색(BST)

이진 탐색 (Binary search) 개념 및 구현
이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘입니다.

이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다.

동작 방식

이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾습니다.

중간 값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있습니다.

이진 탐색의 동작 방식은 다음과 같습니다.

1. 배열의 중간 값을 가져옵니다.
2. 중간 값과 검색 값을 비교합니다.
3. 중간 값이 검색 값과 같다면 종료합니다. (mid = key)
4. 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (mid < key)
5. 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색합니다. (mid > key)
6. 찾거나 간격이 비어있을 때까지 반복합니다.

전체코드

input = sys.stdin.readline

n = int(input())
arr_n = list(map(int, input().split()))
m = int(input())
arr_m = list(map(int, input().split()))
arr_n.sort() #정렬

#이진탐색
for num in arr_m:
    lt = 0
    rt = n - 1 
    isExist = False

    while lt <= rt:
        mid = (lt + rt)//2 #이분탐색의 핵심, mid 설정
        if num == arr_n[mid]:
            isExist = True
            print(1)
            break
        elif num > arr_n[mid]:
            lt = mid + 1
        else:
            rt = mid - 1
    
    if not isExist :
        print(0)