졍's 기술 블로그

수 찾기

티어 : Silver 4
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 자료 구조, 이분 탐색, 트리를 사용한 집합과 맵

문제

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

입력

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

출력

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

예제 입출력

Algorithm

1. bisect 사용
2. A List sort
3. bisect_left와 bisect_right의 값을 비교해 같으면 0, 다르면 1 출력

Code

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline

# 입력
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))

# A 정렬
A.sort()
for i in B:
    left = bisect_left(A, i)
    right = bisect_right(A, i)
    
    # left와 right의 값이 다르면 존재한다는 의미 -> 1 출력
    if left != right:
        print(1)
    else: # 값이 같으면 존재하지 않는다는 의미 -> 0 출력
        print(0)

메모리: 48360 KB
시간: 308 ms