[Python/파이썬] 백준 1920 - 수 찾기

문제 설명

 

1920번: 수 찾기

 

---

풀이 코드

이 문제의 주어지는 입력값의 허용 범위를 보면 100,000으로 시간복잡도OlogN 이나 O(n)으로 풀어야 한다.

그리고 모든 정수의 범위를 보면  -2^31 보다 크거나 같고 2^31보다 작다고 한다.

정수의 범위가 크기 때문에 OlogN의 시간복잡도를 갖는 이분탐색으로 이 문제를 해결하였다.

 

이분탐색 알고리즘에 대해 알고 싶다면 아래 링크를 참고하길 바란다.

[알고리즘] Binary Search(이진 탐색/이분 탐색)이란?

 

 

 

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
N_nums = list(map(int, input().split()))
N_nums.sort() # 이분 탐색은 탐색하고자 하는 리스트가 정렬되어 있어야 한다.

M = int(input())
M_nums = list(map(int, input().split()))

def binarySearch(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = low + (high - low) // 2

        if arr[mid] == target:
            return True

        if target < arr[mid]:
            high = mid - 1
        if target > arr[mid]:
            low = mid + 1
    
    return False

for i in range(M):
    if binarySearch(N_nums, M_nums[i]):
        print(1)
    else:
        print(0)

 

bisect 라이브러리를 활용한 코드

파이썬에서 이진 탐색을 쉽게 구현할수 있도록 제공하는 bisect 라이브러리를 사용하여 다음처럼 쉽게 이진 탐색을 적용할 수 있다.

 

bisect의 함수인 bisect_left(arr, val), bisect_right(arr, val) 들이 가장 많이 사용되며 이 메서드의 기능은 다음과 같다.

• bisect_left(arr, val) : 리스트 arr에서 왼쪽에서 부터 val를 찾아 인덱스 반환
• bisect_right(arr, val) : 리스트 arr에서 오른쪽에서 부터 val를 찾아 인덱스 반환

import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

N = int(input())
N_nums = list(map(int, input().split()))
N_nums.sort() # 이분 탐색은 탐색하고자 하는 리스트가 정렬되어 있어야 한다.

M = int(input())
M_nums = list(map(int, input().split()))

def binarySearch(arr, val):
    left = bisect_left(arr, val)
    right = bisect_right(arr, val)
    return right - left


for i in range(M):
    if binarySearch(N_nums, M_nums[i]):
        print(1)
    else:
        print(0)

여기서 right - left로 arr에서 찾고자하는 val의 개수도 구할 수 있다.