[백준/Python] 10815번 숫자 카드 문제

■ 10815번 숫자 카드 문제

 

출처: 백준 10815번 숫자 카드 문제

 

■ 코드 풀이

 

문제를 보자마자 느낀 것은 배열의 크기가 비정상적으로 크다는 것이었습니다. 그러나 아무리 궁리해서 풀어도 시간 초과가 나오더군요. 그래서 인터넷에서 찾으니, 이 문제의 핵심은 '큰 배열을 얼마나 효과적으로 탐색할 수 있는가'였습니다. 그리고 여기서 이진 탐색이라는 기초적인 알고리즘에 대해 배웠습니다.

이진 탐색은 오름차순으로 정렬된 리스트의 목록에서 절반씩 탐색 범위를 줄여가며 목표를 찾습니다. 자세한 설명은 코드 아래에 링크로 넣어두었습니다.

아래는 코드입니다. 핵심은 while문인데, 중간 지점을 갱신하는 과정입니다. 중간 지점이라 함은 start와 end 포인트의 절반 지점을 의미합니다. 예를 들면, 0과 100 사이의 범위에서 목표가 77일 경우 중간 지점인 50과 77을 비교합니다. 77은 50보다 크기 때문에 탐색 범위를 50에서 100 사이로 옮깁니다. 다시 50과 100의 중간 지점인 75와 목표 숫자인 77을 비교합니다. 77이 여전히 크기 때문에 탐색 범위를 75에서 100 사이로 좁힙니다. 이런 식으로 반복하는 과정을 while문에 구현했습니다.

 

import sys

def Binary_Search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return False


N = int(input())
num_list = list(map(int, sys.stdin.readline().split()))
M = int(input())
check_list = list(map(int, sys.stdin.readline().split()))

num_list.sort()




for i in range(M):
    if Binary_Search(num_list, check_list[i], 0, N - 1) is not False:
        print(1, end=' ')
    else:
        print(0, end=' ')

 

 

이진 탐색 - 나무위키 (namu.wiki)

이진 탐색 - 나무위키