본문 바로가기

알고리즘/알고리즘 문제

[python] 백준 > 이분 탐색 > 숫자 카드(10815)

[문제]

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

[나의 풀이]

import sys
input = sys.stdin.readline

N = int(input())
N_arr = sorted(list(map(int, input().split())))
M = int(input())
M_arr = list(map(int, input().split()))

for marr in M_arr:
    answer = 0
    start = 0
    end = len(N_arr) - 1
    while start <= end:
        mid = (start + end) // 2
        if N_arr[mid] > marr:
            end = mid-1
        elif N_arr[mid] < marr:
            start = mid+1
        else:
            answer = 1
            break
    print(answer, end=' ')
  • 이분탐색 문제이다.
  • M_arr에 있는 것을 하나씩 꺼내어 N_arr에 존재하는지 이분탐색을 통해 확인하고 있으면 1, 없으면 0을 print해준다.