[맛있는물회] [파이썬] <백준 알고리즘> 1920번 "수 찾기"

문제 조건

---

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

Input

---

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

Output

---

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

 

생각한 아이디어

---

당연히 브루트포스로 풀면 안되니깐 정답률이 28프로겠지??

 

이분탐색느낌..

 

솔직히 이분탐색이라는 힌트만 얻으면 쉽게 풀수 있는 문제이다.

 

입력받는 arr값을 정렬해준 다음 이분탐색으로 log(n)의 시간복잡도로 n개를 풀면 nlog(n)이니깐 충분히 가능!

 

 

이진탐색 문제가 진짜 꼬아서 나오면 정말 답도 없게 어려울 듯 하다..

많이 풀어보자!

 

소스코드

import sys
import operator
input=sys.stdin.readline

def find(target,arr):
   front,rear=0,len(arr)-1
   flag=0
   while rear>=front:
      mid=(front+rear)//2
      if arr[mid] >= target:
         if arr[mid]==target:
            flag=1
            break
         rear=mid-1
      else:
         front=mid+1
   return flag

if __name__ == "__main__":
   n=int(input())
   arr1=list(map(int,input().split()))
   m=int(input())
   arr2=list(map(int,input().split()))

   arr1=sorted(arr1)
   for a in arr2:
      print(find(a,arr1))

 

*파이썬 문법 정리