[10815] 숫자 카드

문제

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

입력
5 (숫자 카드의 수)
6 3 2 10 -10 (숫자 카드 종류)
8 (예측 카드의 수)
10 9 -5 2 3 4 5 -10 (상근이가 가지고 있을거라 예측되는 숫자카드의 종류)

출력 (0:틀림, 1:맞음)
1 0 0 1 1 0 0 1

문제 정리

• 이분, 이진 탐색 그 자체이다.
• for문을 통한 반복적 접근법과 재귀를 통해서 푸는 방법 등이 있다.

이진 탐색:

• 입력된 배열 정렬
• 시작 인덱스, 중간 인덱스(소수점 제외), 끝 인덱스 설정
• 찾고자 하는 수의 값이
  • 시작~중간 사이에 있다면 끝 인덱스를 중간인덱스 -1 로 설정
  • 중간~끝 사이에 있다면 시작 인덱스를 중간인덱스+1로 설정
• 시작 인덱스의 값이 끝 인덱스의 값보다 작거나 같을 때까지 2~3반복
• 종료 조건은
  • 시작 인덱스의 값이 끝 인덱스의 값보다 작거나 같을 때
  • 중간 인덱스의 값이 찾고자 하는 값일때

문제 풀이

def binary_search_loof(num_list, target):
    start = 0
    end = len(num_list)-1
    mid = end // 2
    while start<=end:
        if target == num_list[mid]:
            return 1
        else:
            if target > num_list[mid]:
                start = mid + 1
                mid = (end + start) // 2
            else:
                end = mid - 1
                mid = (end + start) // 2
    return 0

n = int(input())
num_list = list(map(int, input().split()))
num_list.sort()
m = int(input())
guess = list(map(int, input().split()))

for g in guess:
    print(binary_search_loof(num_list, g), end = ' ')