(Python) 백준 1920번 - 수 찾기

문제 링크 : https://www.acmicpc.net/problem/1920

1920번: 수 찾기

풀이

처음에 이진탐색 구현 시에 인덱스를 사용하지 않고, python의 리스트 슬라이싱을 활용한 풀이를 사용했는데 시간 초과가 발생하였다.

리스트 슬라이싱은 지정한 범위의 모든 리스트의 원소를 복사하여 새로운 리스트를 만드는 과정을 거친다고 한다. 그렇기 때문에 시간 초과가 발생한 것이다.

따라서 아래 풀이처럼 슬라이싱한 리스트를 넘겨주는 것이 아닌 low, high의 인덱스값을 넘겨주는 방식을 사용해야했다.

import sys

def bsearch(arr, target, low, high):  # 이진탐색
    mid = (low+high)//2 # low와 high를 2로 나눠주어 중간 인덱스 계산
    if arr[mid] == target: # 찾고자하는 값을 찾으면 
        return 1 # 1 반환
    if low == high: # 계속해서 분할하여 리스트에 값이 하나만 존재하더라도 찾고자하던 값을 찾을 수 없었다면
        return 0 # 0 반환
    elif arr[mid] > target: # 중간에 위치한 값보다 찾고자하는 값이 더 작다면 왼쪽(더 작은) 배열에서 찾기
        return bsearch(arr, target, low, mid)
    else: # 중간에 위치한 값보다 찾고자하는 값이 더 크다면 오른쪽(더 큰) 배열에서 찾기
        return bsearch(arr, target, mid+1, high)

int(sys.stdin.readline())  # 몇개의 정수를 입력받을 것인지 알려주는 것인데 풀이에서 사용하지 않음
arr = sorted(list(map(int, sys.stdin.readline().strip().split(" ")))) # 리스트 정렬
n = int(sys.stdin.readline())
check = list(map(int, sys.stdin.readline().strip().split(" ")))
for i in range(n):
    print(bsearch(arr, check[i], 0, len(arr)-1))