[백준/파이썬] 1920번: 수 찾기

문제

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

풀이

문제를 처음 보자마자 in을 이용하면 아주 빠르게 풀 수 있다고 생각해 in을 이용해 문제를 풀었다.
그러나 시간초과가 발생했고 문제를 다시 살펴보았다.
문제를 다시 보니 N과 M의 범위가 100,000으로 상당히 방대했고 이를 하나하나 다 검사를 하면 시간이 오래 걸린다 판단하였다.
그래서 N 리스트를 set으로 선언해 중복을 없애 시간을 최소화하였다.

정답 코드(in)

import sys
input = sys.stdin.readline

n = int(input())
N = set(map(int,input().split()))
m = int(input())
M = list(map(int,input().split()))

for i in M:
    print(1) if i in N else print(0)

---

풀이2

문제를 다 풀고 알고리즘 분류를 보니 어라

이분 탐색으로도 풀 수 있다는 걸 깨달았다(‼️)
이분 탐색으로 한 번 해결해보자

이분 탐색을 위해 N을 list로 선언 후 정렬해준다.

n = int(input())
N = list(map(int,input().split()))
N.sort()

for문을 선언해 이분 탐색을 실행하면 끝

정답 코드2(이분 탐색)

import sys
input = sys.stdin.readline

n = int(input())
N = list(map(int,input().split()))
N.sort()

m = int(input())
M = list(map(int,input().split()))

for i in M: # M 리스트의 값이 존재하는지 찾기 위해
    l,r = 0, n-1 # 탐색하려는 범위
    while l <= r:
        mid = (l+r) // 2
        if N[mid] == i:	# 찾으려는 값이 mid 값과 일치하면
            print(1) # 1 출력
            break
        elif N[mid] < i: # 찾으려는 값이 mid 보다 크다면
            l = mid + 1 # left 값 증가
        else: # 찾으려는 값이 mid 보다 작다면
            r = mid - 1 # right 값 감소
    else: # 찾으려는 값이 N에 없으면
        print(0) # 0 출력