백준 [1920. 수 찾기] - python

☞ 문제 1920번 : 수 찾기

1920번: 수 찾기

☞ 풀이 

n 크기의 n_list를 입력받아 오름차순 정렬한다. m 크기의 m_list를 입력받는다.이분탐색 알고리즘을 적용한 재귀호출을 통해 m_list 리스트의 원소값들이 n_list에 존재하는지 판단한다.

 

☞ study

▷ 런타임 에러를 막기 위해 input() 대신 sys.stdin.readline()을 사용한다.

▶ 참고 [Python 문법] 파이썬 입력 받기

 

▷ 이분탐색 알고리즘(Binary Search Algorithm)

• 오름차순으로 정렬된 배열에서 탐색 범위를 반으로 줄여가며 특정 값(value)을 찾는 알고리즘이다.
• 처음부터 끝까지 모든 값을 비교하는 순차탐색보다 더 빠르다.
• N 크기의 배열에 대한 이분탐색의 시간복잡도는 O(logN) 이다.
• 배열의 중간 인덱스에 속한 값 mid을 선택하여 찾고자 하는 값 X와 비교한다.
  
  • mid < X : mid 기준으로 오른쪽 값들을 비교한다.
  • mid > X : mid 기준으로 왼쪽 값들을 비교한다.

▷ // 기호를 이용하여 나누기 연산 후 몫의 정수 값만을 반환한다.

▶ 참고 사칙연산을 위한 7가지 연산자

 

☞ 코드

import sys

# 이분탐색 함수
def BinarySearch(num, n_list, left, right):
    if(left > right):
        return False

    mid = (left + right) // 2
    if(n_list[mid] < num):
        return BinarySearch(num, n_list, mid+1, right)
    elif(n_list[mid] > num):
        return BinarySearch(num, n_list, left, mid-1)
    else:        
        return True

# main
n = int(sys.stdin.readline())
n_list = sorted(list(map(int, sys.stdin.readline().split())))
m = int(sys.stdin.readline())
m_list = list(map(int, sys.stdin.readline().split()))

for num in m_list:
    if BinarySearch(num, n_list, 0, n-1):
        print(1)
    else:
        print(0)    

 

☞ 결과

• 맞았습니다!! 
• 메모리 : 44708 KB
• 시간 : 696 ms