1920 - 수 찾기

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

 

1. 문제 이해하기

N개의 정수 A1, A2, ..., AN이 주어져 있음. 이때 정수 M개가 주어졌을 때, 이 수들이 A안에 존재하는지 판단.

 

- 입력 형식

첫째 줄에 자연수 N

둘째 줄에 N개의 정수 A1, A2, ..., AN

셋째 줄에 자연수 M

넷째 줄에 M개의 정수 x1, x2, ..., xM (찾고 싶은 수들)

 

- 출력 형식

M개의 정수에서 각각의 수가 A안에 존재하면 1, 없므녀 0출력

 

A배열 = [4, 1, 5, 2, 3]

찾고 싶은 수들 = [1, 3, 7, 9, 5]

출력 : 1 1 0 0 1

 

A배열에 어떤 수가 존재해야 하는지 파악해야함 --> 자료구조 공부용 이진탐색으로 풀이.

 

생각한 알고리즘

1. 먼저 이진탐색 써야하니까 A배열을 정리함

2. 이진탐색 : M개의 수를 하나씩 꺼내면서 A배열에 있는지 없는지를 찾음

3. 찾으면 1 출력하고 아니면 0

 

 

2. 문제 풀이

def binary_search(array, target):
    left = 0        # 탐색 범위 시작 인덱스
    right = len(array) - 1      # 탐색 범위 끝 인덱스
    while left <= right :
        mid = (left + right) // 2
        if array[mid] == target:
            return True
        elif array[mid] > target:   # 중간값이 찾는 값보다 크면
            right = mid - 1     # right을 mid 왼쪽으로 옮김
        else:                   # 중간값이 찾는 값보다 작으면
            left = mid + 1      # left를 mid 오른쪽으로 옮김
    return False

N = int(input())
A = list(map(int, input().split()))
A.sort()
M = int(input())
target = list(map(int, input().split()))

for item in target:
    if binary_search(A, item):
        print(1)
    else:
        print(0)