수 찾기(백준 1920)

태그

이진탐색

링크

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

체크 필요

문제 출처: https://www.acmicpc.net/problem/1920

문제

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을 출력한다.

예제

입력

Plain Text
복사

출력

Plain Text
복사

풀이

import sys

# input

N = int(sys.stdin.readline())
N_list = list(map(int, sys.stdin.readline().split()))
N_list.sort()
M = int(sys.stdin.readline())
M_list = list(map(int, sys.stdin.readline().split()))


# 이진탐색
def bin_search(N_list, value):
    
    pl = 0
    pr = len(N_list)-1
    
    while (pl <= pr):
        
        mid = (pl+pr)//2
        
        if N_list[mid] > value:
            pr = mid - 1
        elif N_list[mid] < value:
            pl = mid + 1
        else:                   # 검색 성공
            return 1
    
    return 0                   # 검색 실패


# 시간 절약을 위해 dictionary를 생성하여 참조하는 형식으로 하자.
m_dict = {}
for value in M_list:
    
    if value not in m_dict:                 # dictionary에 참조할 값이 없는 경우
        m_dict[value] = bin_search(N_list, value)
        print(m_dict[value])
        
    else:                                   # 이미 dictionary에 참조할 값이 있는 경우
        print(m_dict[value])
Python
복사

기억할 점

•

이진 탐색의 기본을 알고 있다면 굉장히 간단한 문제이다.

•

다만, 시간 초과가 뜰 가능성이 있기 때문에 시간 절약을 위해 이미 검색을 마친 값은 굳이 또 검색하지 않도록 dictionary를 생성하여 참조하는 방식을 사용하였다.