[Python][백준/BOJ] 1920번 : 수 찾기

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

1920번: 수 찾기

 

내 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
m = int(input())
num = list(map(int, input().split()))

def bisect(num):
    flag =0
    start = 0
    end = len(arr)-1
    while start <= end:
        mid = (start + end)//2
        if arr[mid] == num:
            print('1')
            flag =1
            break 
        elif arr[mid] > num:
            end = mid -1
        elif arr[mid] < num:
            start = mid +1
    if flag ==0 :
        print('0')
        
        
for i in num:
    bisect(i)

 

코드 리뷰

해당 문제는 이분탐색에 익숙해지지 않았을..몇 년 전에 틀렸던 문제인데 실패라는 글자가 너무 신경쓰여 풀었다.

이분탐색

문제 자체의 시간 제한으로 인하여 for문을 연속으로 돌려 브루트포스로 찾으면 시간 초과가 뜰 수 있는 문제이다.

그래서 이분탐색으로 접근해야 한다.

나는 이분탐색 함수를 만들어서, num 안의 숫자를 하나씩 꺼내가며 해결했다.

def bisect(num):
    flag =0
    start = 0
    end = len(arr)-1
    while start <= end:
        mid = (start + end)//2
        if arr[mid] == num:
            print('1')
            flag =1
            break 
        elif arr[mid] > num:
            end = mid -1
        elif arr[mid] < num:
            start = mid +1
    if flag ==0 :
        print('0')

이분탐색의 코드는 크게 left, mid, right라는 변수가 사용된다. 나는 start, end 가 더 편해서 이렇게 이름을 지어 사용했다. 

코드를 돌리는 동안에는 mid를 계속해서 움직여주며, 결국 start가 end보다 더 커질 때 종료된다.

mid는 중앙값을 의미하며, 수의 절반 값이 아니라 배열의 중앙 값을 사용하고자 이용된다.

그래서 비교하고자 하는 배열인 arr라는 배열의 중앙값을 계속해서 바꾸어주며, 하나의 num 숫자를 찾아낸다.

찾고자 하는 num이 arr[mid]값보다 더 작다면, 더 작은 숫자로 범위를 좁혀가며 찾아내고, num이 더 크다면 start 값을 더 크게 해서 mid 값을 키워서 큰 숫자로 범위를 좁혀가며 찾아낸다.