10815문제 python - [백준-실버4/이분탐색]

문제 내용 요약

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

입력 :

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

출력 : 

1 0 0 1 1 0 0 1

 

문제 해석

탐색 과정에서 시간복잡도를 고려해야해서 '이진탐색' 을 구현할 수 있어야한다.

이진탐색 알고리즘 구현

이진탐색의 핵심요소 

반복조건 : 전체 리스트 인덱스에서 양 끝의 인덱스가 같거나 / 범위가 넘어갈 때까지 반복

 

탐색조건 3가지:  

 1) target이 중간값과 같을경우 '1 '반환

 2) target이 중간값보다 작을경우   

    리스트 : [-3, 7, 9, 14, 25] / Target : -3인 경우 중간 값인 9 보다 작은 공간 탐색
    오른쪽 공간을 버리고 right 인덱스를 땡기면 됨, right = mid - 1

left = mid + 1

 3) target이 중간값보다 클경우

      리스트 : [-3, 7, 9, 14, 25] / Target : 14인 경우 중간 값인 9 보다  큰 공간 탐색

    왼쪽 공간을 버리고 left인덱스를 땡기면 됨, left = mid + 1

# 탐색하고자 하는 리스트 정렬
list = sorted(list)

def bin_search(list, target):
	length = len(list)
    
    # 양끝 배열의 인덱스 right 인덱스 = (총길이 - 1)
    left = 0 
    right = length -1
    mid = right + left) // 2
    
    
    # 탐색하다 Target과 같은 값이 나오거나 안나올 때까지 반복 
    while left <= right:
    	# 3개의 조건 존재 target이 중간값과 같을경우 '1 '반환
        # target이 중간값보다 작을경우
        # target이 중간값보다 클경우 
        
    	if list[mid] == target:
        	return '1 '
            
        elif list[mid] > target:
        	right = mid - 1
        
        elif list[mid] < target:
        	left = mid + 1
            
    # 조건을 벗어나면 같은 값이 없으므로 ' 0'반환
    return ' 0'

 

정수 M의 값을 하나하나 탐색

 

import math

a = int(input())
n_list = list(map(int, input().split(" ")))

c = int(input())
m_list = list(map(int, input().split(" ")))

n_list = sorted(n_list)

answer = ''
for val in m_list:
	
    # 위의 bin_search확인
    val2 = bin_search(n_list, val)
    answer += str(val2)
    
print(answer)

깨달은 것

시간복잡도 영향을 미치는 문제의 경우 '이진탐색'을 고려해야 한다. 한번 알아놓으면 어려운 코드는 아니니 쉽고 응용하기도 쉬울것 같다. 특정 리스트에서 값을 찾을 때 활용하면 될 것 같다.