백준 1920번: 수 찾기 (python, 파이썬)

• 문제

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

---

• 코드

def check(num):
    # 맨 왼쪽 low index
    # Leftmost index
    low = 0

    # 맨 오른쪽 right index
    # Rightmost index
    high = N-1

    answer = 0
    while(True):
        # 가운데 index 설정
        # Set middle index
        mid = (low + high) // 2

        # low가 high보다 크면 반복문 종료
        # If low is over high then exit while loop
        if low > high:
            break
        if A[mid] == num:
            answer = 1
            break
        # 정답이 중간단계보다 작다면 high index를 mid에서 1을 빼준다
        elif A[mid] > num:
            high = mid - 1
        # 정답이 중간단계보다 크다면 low index를 mid에서 1을 더해준다
        else:
            low = mid + 1
    return answer

N = int(input())
A = list(map(int, input().split(' ')))
# 오름차순 정렬
# Ascending sort
A.sort()

M = int(input())
B = list(map(int, input().split(' ')))
for i in B:
    print(check(i))

 

일일히 반복하면서 brute force방식으로 값을 찾을 수 있지만 시간초과가 뜰것이다.

이분탐색을 이용해 중간의 값을 찾아서 정답과 계속 비교해가면 low, high index를 조정하면 시간이 단축된다.

 

정답이 중간단계보다 작다면 중간단계 이후로는 값을 살펴볼 필요가 없기 때문에 high index를 mid index에서 1을 빼주는 것이고

정답이 중간단계보다 크다면 중간단계 이전에는 값을 살펴볼 필요가 없기 때문에 low index를 mid index에서 1을 더해주는 것이다.

---

• 출처

www.acmicpc.net/problem/1920