[Python] 백준 #1920 수 찾기

 🌙 수 찾기 🚀

 

 💬 Problem

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

 

 💸 Limit

• 입력: 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A [1], A [2], …, A [N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
• 출력: M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
• 시간 제한: 2 초
• 메모리 제한: 128 MB

 🌱 Code

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
a.sort() #이진탐색을 쓰기 위해서는 정렬된 리스트를 가져와서 사용해야한다.

m = int(sys.stdin.readline())

b = list(map(int, sys.stdin.readline().split()))

for i in b: # 비교 대상 리스트를 i에 하나씩 대입
    start, end = 0, n-1 # 리스트의 시작점, 끝점 인덱스
    flag = True # flag로 츨력값 컨트롤
    while start <= end: # 리스트의 비교 시작점이 끝점을 넘어서면 종료
        mid = (start + end) // 2 # 중간점 -> 정수값
        if a[mid] < i: # 중간점에 해당하는 값이 찾는 대상보다 작으면
            start = mid + 1 # 시작점에 중간점+1을 대입 -> 범위 축소
        elif a[mid] > i: # 중간점에 해당하는 값이 찾는 대상보다 크면
            end = mid - 1 # 끝점에 중간점-1을 대입 -> 범위 축소
        else: # a[mid] >= i, a[mid] <= i, a[mid] == i
            print(1)
            flag = False
            break
    if flag is True:
        print(0)
'''
제일 중요한건 이 문제가 왜 이분/이진탐색으로 풀어야 하는지를 깨달아야 한다.
'''
'''
이건 처음에 푼 방법인데 시간초과로 실패함 -> 이분 탐색 사용하자!

num = 0
for i in range(N):
    for j in range(M):
        if check_l[i] == A[j]:
            num = 1
            print(num)
            break
        num = 0
    if num == 0:
        print(num)
'''​

 

 🌠 Solution

이분 탐색을 사용해야 시간 초과가 뜨지 않는다.