백준 1920번 수 찾기

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

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

import sys


n = int(input())
num_list =map(int, sys.stdin.readline().split())
num_list.sort() 
m = int(input())
chk_list = map(int, sys.stdin.readline().split())
result_list=[]

for i in chk_list:
    start=0
    end=len(num_list)-1
    while True:
        mid = (start+end)//2

        if start > end:
            sys.stdout.write("0"+"\n")
            break
        elif num_list[mid]==i:
            sys.stdout.write("1"+"\n")
            break
        elif i < num_list[mid]:
            end = mid-1
        else:
            start = mid+1

저는 Binary Search를 이용하여 풀었지만 set자료형을 활용하여 간단히 풀 수도 있습니다.

하지만 Binary Search의 개념을 직관적으로 알기 좋아 Binary Search를 사용하여 풀어보겠습니다.

 

문제풀이

Binary Search문제는 보통 많은 양의 데이터를 확인해야 할때 사용합니다.

따라서 입력의 수가 많은 경우가 많으므로 input()이 아닌 sys.stdin.readline()을 활용해서 입력을 받습니다.

 

또한 Binary Search는 정렬된 자료구조에만 사용할 수 있으니 입력받은 리스트를 정렬시켜 줍니다.

 

이후 검사해야 할 값을 하나씩 순회하며 이진 탐색합니다.

• 시작과 끝의 index를 더한 다음 반을 나눈 몫을 int형으로 받습니다.
• num_list[mid]보다 i의 값이 작다면 end를 mid-1로 설정합니다
• num_list[mid]보다 i가 클시엔 start를 mid+1로 설정합니다

 

값을 찾았거나 값이 num_list에 없는 경우 출력 후 break 합니다.

• start가 end보다 커질 시에는 i가 리스트에 없는 것이므로 0을 출력하며
• num_list[mid]와 i가 같을 시에는 1을 출력하고 break 합니다.