[BOJ] 1920. 수 찾기

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

1920번: 수 찾기

 

 

1. 해결방법

"""
1. 아이디어
- M 배열을 for문 돌린다.
- 시간복잡도를 고려해서 N개의 배열을 정렬해서 이진탐색을 활용한다.

2. 시간복잡도
- O(NlogN)
"""

 

2. 정답코드

import sys
input = sys.stdin.readline

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


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

    mid = (start + end) // 2
    if nums[mid] < tar:
        search(mid + 1, end, tar)
    else:
        search(start, mid, tar)


for target in targets:
    search(0, N - 1, target)

이 문제는 이진탐색의 기본이 되는 문제라고 보면된다. 
투포인터와 마찬가지로 시간복잡도를 판단하고 이진탐색을 써야하는 것을 알아야 한다. 이진 탐색을 사용하기 위해서는 배열의 정렬화도 매우 중요하다.