[코딩테스트] 백준 2559번: 수 찾기

1. 아이디어

▪ N개의 정수 정렬

▪ for문 돌면서 이진탐색 M번 수행

▪ 이진탐색

   - 존재하면 1 출력

   - 존재하지 않으면 0 출력

2. 시간복잡도

▪ N개 입력값 정렬 = O(NlogN)

▪ M개를 N개 중에서 탐색 = O(MlogN)

▪ O(NlogN+MlogN) = O(N+M(logN)) = O(2e5*log2e5) = O(4e6)

3. 변수

▪ 자연수 배열: int[]

▪ 찾는 수 배열: int[]

Code

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int,input().split()))
M = int(input())
find_nums = list(map(int,input().split()))

nums.sort()

def bis(start,end,num):
    if start == end:
        if nums[start] == num:
            print(1)
        else:
            print(0)
        return

    mid = (start+end)//2

    if nums[mid] < num:
        bis(mid+1, end, num)
    else:
        bis(start, mid, num)

for num in find_nums:
    bis(0,N-1,num)

 

1920번: 수 찾기