[🥈4 / 백준 1920 / 파이썬] 수 찾기

 

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을 출력한다.

 

예제 입력 5 4 1 5 2 3 5 1 3 7 9 5

예제 출력 1 1 0 0 1

 

풀이

 

이분 탐색을 통해 배열에 특정 수의 존재 여부를 판별하는 문제이다.

 

리스트의 목록을 하나씩 비교하며 찾는다면 시간 복잡도가 O(n^2)일 것이므로 시간 초과가 발생할 것이다.

따라서 더욱 효율적인 이분 탐색을 활용하도록 하자.

 

우선 기본적으로 이분 탐색을 하기 위해서는 리스트가 정렬되어 있어야 한다.

이진 트리를 생성하는 방법은 아래와 같다.

 

 

비교할 숫자를 루트부터 비교하여 비교 숫자가 더 크다면 오른쪽 자식 노드로, 작다면 왼쪽 자식 노드로 찾아가면 된다.

만약 끝 자식 노드까지 찾았는데 숫자가 없을 경우 이전 인덱스를 똑같이 반환하게 되거나 리스트를 벗어나게 되므로 이 경우 0을 출력하도록 하자.

 

import sys,random
input = sys.stdin.readline

n = int(input())
A = list(map(int,input().split()))
m = int(input())
B = list(map(int,input().split()))

A.sort()

for i in B:
    start = 0
    end = len(A)
    mid = (start + end)//2
    check = (start,end)
    # 끝 자식노드인지 체크

    while(True):
        try:
            if A[mid] == i:
                print(1)
                break
        except:
            print(0)
            break
            # 인덱스가 리스트를 벗어나는 경우
            
        if A[mid] < i:
            start = mid + 1
        elif A[mid] > i:
            end = mid - 1
        if (start,end) == check:
            print(0)
            break
            # 인덱스가 이미 끝 노드인 경우
            
        check = (start, end)
        
        mid = (start + end)//2