[Algorithm] [Python] 백준/BOJ - 1966 _ 수 찾기

1966 - 수 찾기

---

INDEX

---

• 문제
• 입력
• 출력
• 예제 입출력
• 제출 코드
• 문제 풀이

문제

---

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

예제 입출력

---

입력 :
5
4 1 5 2 3
5
1 3 7 9 5

출력 :
1 1 0 0 1

제출 코드

---

from sys import stdin

def bin_search(s, n, start, end):
    if start > end:
        return 0
    mid = (start + end) // 2
    if s[mid] > n:
        return bin_search(s, n, start, mid-1)
    elif s[mid] < n:
        return bin_search(s, n, mid+1, end)
    else:
        return 1


N = int(stdin.readline())
Narr = list(map(int, stdin.readline().split()))
M = int(stdin.readline())
Marr = list(map(int, stdin.readline().split()))

Narr.sort()


for i in Marr:
    print(bin_search(Narr, i, 0, N-1))

문제 풀이

---

그냥 바로 떠올랐던 순차탐색을 통해 문제를 풀면 시간초과가 뜬다.

이후, 알고리즘 분류가 이분 탐색으로 되어있는것을 보고 바로 이분 탐색을 통해 풀었다.

이분 탐색 함수의 인자로 비교 배열, 찾고자 하는 숫자 그리고 배열의 시작과 끝 인덱스를 전달한다.

만일, 배열의 시작 인덱스갑이 끝 인덱스값 보다 큰 경우에는 0을 반환한다.

이후 mid 피벗을 설정하고 비교할 숫자(i)가 arr[mid] 값보다 큰 경우와 작은 경우에 대하여 분기를 진행한다.

만일 i 가 더 크다면 start 값을 조정하고, i가 더 작다면 end값을 조정하여 다시 이분 탐색을 진행하도록 한다.

이러한 반복을 통해 만일 동일한 값을 찾게되면 1을 반환한다.

이분 탐색 진행 전, 배열을 오름차순 정렬해주는 것을 잊지말자!