[1920] 수 찾기

문제

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

입력
5 (정수의 수)
4 1 5 2 3 (실제 정수 값)
5 (예측 하려는 수)
1 3 7 9 5 (예측 정수 값)

출력
1
1
0
0
1

문제 정리

• 이분 탐색으로 접근하면 된다.
• 정렬가능한 문제이고 시간제한이 있다면 이분 탐색이 O(log N)으로 큰 데이터셋에서 매우 빠르기에 그렇다.
• 또는 set(파이썬에서는 set자료형이 해쉬 테이블로 구현됨)을 활용하여 구현한다.

문제 풀이

첫번째 풀이

재귀를 이용한 이분 탐색을 진행하였다. 이것이 문제에서 진정으로 원하는 방식이다.

# 이분 탐색을 재귀로 구현
def recursion_binary_search(num_list, start, mid, end, target):
    if num_list[mid] == target: # 종료조건 1 : target을 찾은 경우
        return 1
    elif start > end:
        return 0
    elif num_list[mid] > target: # 종료조건 2 : 다 탐색했음에도 target을 못찾은 경우
        end = mid - 1  
        mid = (end+start)//2
        return recursion_binary_search(num_list, start, mid, end, target)
    else:
        start = mid+1
        mid = (end+start)//2
        return recursion_binary_search(num_list, start, mid, end, target)

n = int(input())
num_list = list(map(int, input().split()))
m = int(input())
guess = list(map(int, input().split()))
num_list.sort()
start = 0
end = len(num_list)-1
mid = end//2
for target in guess:
    print(recursion_binary_search(num_list, start, mid, end, target))

두번째 풀이

set을 이용하여 순차적인 접근방식을 이용하였다.
list를 이용하여 순차적인 접근을 한다면 무조건 시간초과가 나오지만
파이썬에서는 set이 해시 테이블 기반 구현이 되어있다.
때문에 요소의 검색, 삽입, 삭제에 대해 평균적으로 O(1)의 시간 복잡도를 가진다. 이는 배열이나 리스트에서 요소를 검색할 때 필요한 O(N)의 시간 복잡도보다 훨씬 빠르고 중복까지 제거가 되었기에 통과가 되었다.

n = int(input())
num_list = set((map(int, input().split())))
m = int(input())
guess = list(map(int, input().split()))
for g in guess:
    if g in num_list:
        print(1)
    else:
        print(0)