[Python] [백준] 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을 출력한다.

---

그냥 list를 사용하면 시간초과가 발생한다.

list로 하나씩 비교하면 O(N)시간이 걸리기 때문이다.

 

하지만 이진탐색을 사용한다면,

O(logN) 시간이 걸려 더 빠르게 탐색할 수 있다.

logN은 트리구조로 탐색할 때의 특징이다.

 

시간복잡도의 효율을 보자면 이렇다

O(1)	O(logN)		O(N)	O(NlogN)	O(N²)	O(N³)	O(2ⁿ)
상수	로그		선형	로그선형		이차	삼차	지수

로그가 더 빠르다.

 

1. 이진 탐색 - 재귀함수

• 기본적으로 시간을 줄이기 위해 sys.stdin.readline() 을 사용했다.
• 그리고 이진 탐색을 사용하기 위해 이진 탐색에 사용할 리스트(arr1)를
  입력받자마자 정렬했다. sorted() 를 하면 정렬된 리스트를 반환한다.
• time은 시간측정을 위해 넣었다.
• 이진 탐색 함수를 만들었다.
  인자는 배열, 찾고자 하는 target, 시작점, 끝점 이다.
  1. 시작점이 더 큰 경우는 말이 안 되므로 실패값을 반환
  2. 이진탐색의 핵심인 중간을 만듦
  3. target이 중간점과 같다면 바로 성공값을 반환
     arr1이 정렬되어 있기에 이렇게 탐색이 가능하다.
  4. 중간점보다 target이 작으면 왼쪽 탐색함
     왼쪽을 탐색하기 위해 끝값을 중간-1로 설정
  5. 반대라면 오른쪽을 탐색함
     오른쪽을 탐색하기 위해 시작값을 중간+1로 설정
  6. 이때 재귀함수(함수내 같은 함수)를 사용한다.
• 실행코드에서 시작값: 0, 끝값: 길이-1 를 정해놓고,
  탐색할 배열, target값, 시작값, 끝값을 함수의 인자로 넘겨준다.

import sys, time

N = int(sys.stdin.readline())
arr1 = sorted(map(int, sys.stdin.readline().strip().split(' ')))    # 정렬하여 list로 저장
M = int(sys.stdin.readline())
arr2 = list(map(int, sys.stdin.readline().strip().split(' ')))

start_time = time.time()    # 측정 시작

def binary(arr, target, start, end):
    if start > end:
        return 0    # 탐색실패
    mid = (start+end)//2    # 이진 탐색의 핵심. 반으로 나눔
    # 바로 찾으면 중간점 인덱스 반환
    if target == arr[mid]:
        return 1    # 탐색성공
    # target이 중간보다 작으면 왼쪽만 탐색
    elif target < arr[mid]:
        return binary(arr, target, start, mid-1)
    # target이 중간보다 크면 오른쪽만 탐색
    elif target > arr[mid]:
        return binary(arr, target, mid+1, end)

for target in arr2:
    # 이진 탐색의 범위
    start = 0
    end = N-1  # 인덱스와 관련이 있으므로 '길이-1'로 넘긴다.
    # 이진 탐색 함수의 인자:
    # 정렬된 배열, 타겟, 시작점, 끝점
    print(binary(arr1, target, start, end))



end_time = time.time()      # 측정 종료
# print("time:", end_time - start_time)   # 수행 시간 출력

---

2. 이진 탐색 - 반복문

재귀함수와 비슷하지만 왼쪽, 오른쪽을 탐색할 때

start, end 값만 바꾸어 반복문을 실행한다.

import sys, time

N = int(sys.stdin.readline())
arr1 = sorted(map(int, sys.stdin.readline().strip().split(' ')))    # 정렬하여 list로 저장
M = int(sys.stdin.readline())
arr2 = list(map(int, sys.stdin.readline().strip().split(' ')))

start_time = time.time()    # 측정 시작

def binary(arr, target, start, end):
    while start <= end:
        mid = (start+end)//2
        # 바로 찾으면 반환
        if target == arr[mid]:
            return 1
        # target이 중간보다 작으면 왼쪽만 탐색하도록 끝점을 바꿈
        elif target < arr[mid]:
            end = mid-1
        # target이 중간보다 크면 오른쪽만 탐색하도록 시작점을 바꿈
        elif target > arr[mid]:
            start = mid+1
    return 0

for target in arr2:
    # 이진 탐색의 범위
    start = 0
    end = N
    # 이진 탐색 함수의 인자:
    # 정렬된 배열, 타겟, 시작점, 끝점
    print(binary(arr1, target, start, end-1))
    # 인덱스와 관련이 있으므로 end-1로 넘긴다.


end_time = time.time()      # 측정 종료
# print("time:", end_time - start_time)   # 수행 시간 출력

---

3. 집합 이용

값을 찾을 때 순서 상관없이 존재만 하면 되므로 set을 사용한다.

리스트를 변경할 일이 없으므로 검색속도가 빠른 tuple을 사용한다.

 

그렇게 tuple 자료형인 arr2의 값을 하나씩 꺼내면서

set 자료형인 arr1에 있는 값인지 확인하여

있으면 1 출력, 없으면 0 출력함

import sys
N = int(input())
arr1 = set(map(int, sys.stdin.readline().strip().split(' ')))
M = int(input())
arr2 = tuple(map(int, sys.stdin.readline().strip().split(' ')))
for i in arr2:
    if i in arr1:
        print(1)
    else:
        print(0)