백준 10815 숫자카드 파이썬 문제풀이 (python 이분탐색)

문제 보러가기

 

백준 숫자카드 파이썬 문제풀이

이 문제는 N개의 숫자 카드들을 입력 받고 나서

M개의 숫자들을 입력 받으면, 각 숫자들에 대해서

숫자 카드에서 찾을 수  있는 숫자인지를 체크하는 문제이다.

 

로직은 단순하지만, N,M의 수가 10,000,000이기 때문에 시간이 중요한 문제이다.

즉 탐색 중 시간이 덜 걸리는 이분탐색을 사용해야한다.

 

정답코드

n = int(input())
card = list(map(int,input().split()))
card.sort()
m = int(input())
num = list(map(int, input().split()))
result = []
for find in num:
    mid = int(n / 2)
    start = 0
    end = n-1
    while start < end:
        if card[mid] == find:
            break
        if card[mid] > find:
            end = mid
            mid = (start + end) // 2
        elif card[mid] < find:
            start = mid + 1
            mid = (start + end) // 2

    if card[mid] == find:
        result.append(1)
    else:
        result.append(0)
print(result)

start, mid, end 인덱스를 이용해서 

이분탐색을 구현하였다.

 

이분탐색은 처음과 끝 인덱스를 각각 잡은 뒤,

중간 값을 정해서 목표하는 값과 일치하는지 보고,

 

중간값이 목표값보다 크면 end를 mid로

목표값보다 작으면 start를 mid+1 로 인덱스를 변경해서

 

배열을 절반으로 분할하면서 원하는 값을 찾는 탐색 방법이다.

 

이분탐색 방법은 정확히 구현했나보다. 

 

보니까 end = mid로 해도 되고,

end = mid - 1로 해도 이분탐색이 성립되는 것 같다. 

 

end = mid - 1의 경우 (start+end)/2 하다가 지나치는 숫자가 생기는데, 

그런 경우 다시 start를 업데이트해서 올라와 탐색한다.