백준_1920_수찾기/Using_Python_파이썬

Problem

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

1920번: 수 찾기

 

About Problem

input에서 N이 최대 100000 이고 M이 최대 100000이므로 결국 Output을 0 또는 1로 판단하기 위해서는 M에 들어 있는 숫자를 다 찾아야한다. 하지만 둘다 최대일 때는 100억번을 반복해야 하므로  완전 탐색으로 찾을 수 없다.

그래서 정렬을 하고 빅오를 줄 일 수있는 이분탐색을 통해서 index를 찾기로 결정했다.

Code

from sys import stdin

# 입력받기
N = int(stdin.readline())
lst = list(map(int, stdin.readline().split()))
M = int(stdin.readline())
find_lst = list(map(int, stdin.readline().split()))

# 정답 list
answer = [0] * M
# list 정렬해서 이분탐색으로 문제 풀이
lst.sort()

# M번 반복해서 찾기
for i in range(M):
    # 스타트를 0, 끝은 N-1로 설정
    s, e = 0, N - 1
    # target을 find_lst i번째 인덱스로 설정
    target = find_lst[i]

    # 이분탐색
    while s <= e:
        mid = (s+e) // 2

        if lst[mid] == target:
            answer[i] = 1
            break

        elif lst[mid] > target:
            e = mid - 1

        else:
            s = mid + 1
    print(answer[i])