백준-BOJ 1920번 수 찾기 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 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을 출력한다.

예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 

1
1
0
0
1

---

문제 설명

문제는 간단하다 배열로 수를 받는다고 생각하면 A라는 배열에 M의 수가 있는지 확인하고 있다면 1 없다면 0을 출력하면 된다. 처음에는 단순히 두개의 for문을 통해 완전 탐색으로 배열을 돌며 i 값을 찾아내는 방식으로 풀이하려고 하였으나 시간 초과를 맛보고 이분 탐색법으로 풀이를 하였다. 이분 탐색을 하는 함수에서 정렬을 하려다가 또 시간 초과를 경험했다 이 점을 주의해야 할 것 같다.

 

풀이

def binary_search(target, data):
    start = 0
    end = n - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return True

        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return False

import sys
input = sys.stdin.readline

n = int(input())
a = sorted(list(map(int, input().split())))

m = int(input())
a2 = list(map(int, input().split()))

for i in a2:
    if binary_search(i, a):
        print(1)
    else:
        print(0)

 

풀이 설명

이분 탐색

이분 탐색은 처음부터 모든 수를 비교하는 선형 탐색과는 다르게 수의 대소를 비교하여 범위를 좁히며 수를 찾는 방법이다. 범위가 줄어 선형 탐색은 시간 복잡도가 O(N)이지만 이분 탐색은 O(logN)이다. 이분 탐색을 위해서는 항상 오름차순으로 정렬되어 있어야 한다.

 

이분 탐색

간단하게 설명하자면 left와 right의 절반인 mid를 설정하고 찾고자 하는 수가 5보다 크다면 오른쪽 그림과 같이 left를 다시 설정하고 범위를 좁혀 탐색을 실행한다. 만약 5보다 작다면 이 반대로 right가 이동하게 된다.

 

이론을 토대로 코드를 작성하면 a2의 배열의 수들을 선회하며 binary_search 함수를 실행하고 이 함수의 조건문을 통해서 left(start)와 right(end)를 mid 값을 이용하여 포인터를 조정하고 값을 찾으면 True 없다면 False를 리턴하여 1과 0을 출력한다.

---

풀이 결과

1920 풀이 결과