[백준] [파이썬] [이분탐색] [정렬] 1920번: 수 찾기

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^{31} 보다 크거나 같고 2^{31}보다 작다.

출력

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

예제 입력 1

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

예제 출력 1

1
1
0
0
1

 

---

 

입력 수가 굉장히 크기 때문에 

import sys 
sys.stdin=open('input.txt', 'r')


if __name__=="__main__":
    N = int(input())
    A = list(map(int, input().split()))
    M = int(input())
    check = list(map(int, input().split()))
    
    
    for c in check:
        if c in A:
            print(1)
        else:
            print(0)

 

이런식으로 하면 무조건 시간 초과 걸릴 것이라는게 예상이 간다.

 

이제 저렇게 큰 입력과 검색은 이분탐색이라는 것이 패턴화 되었다. 

 

import sys 
sys.stdin=open('input.txt', 'r')


if __name__=="__main__":
    N = int(input())
    A = list(map(int, input().split()))
    M = int(input())
    check = list(map(int, input().split()))
    
    A.sort()
    for c in check:
        flag=0
        start = 0
        end = N-1
        while start<=end:
            mid = (start + end) // 2
            if A[mid] == c:
                print(1)
                flag=1
                break
            elif A[mid] > c:
                end = mid-1
            elif A[mid] < c:
                start = mid+1
        
        if flag==0:
            print(0)