[백준/Python] 10815 숫자 카드

[백준/Python] 10815 숫자 카드

풀이 코드 및 설명

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(sys.stdin.readline())
n_arr = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_arr = list(map(int, sys.stdin.readline().split()))

n_arr.sort()

for i in range(m):
    if Binary_Search(n_arr, m_arr[i], 0, n-1) is not False:
        print(1, end=' ')
    else:
        print(0, end= ' ')

위 문제를 읽고 입력을 읽었다. N과 M 이 최대 500,000가 될 수 있고, 숫자 카드에 적힌 수가 무려 -10,000,000 보다 크거나 같고 10,000,000 보다 작거나 같다.

입력의 크기가 매우 큰 것이다. 또한 이 문제에는 시간 제한 2초를 가지고 있다.

처음엔 단순히 아래 코드와 같이 문제를 풀었다.

import sys

n = int(sys.stdin.readline())
n_arr = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_arr = list(map(int, sys.stdin.readline().split()))

result = [0] * m
for i in range(m):
    if m_arr[i] in n_arr:
        result[i] = 1
    else:
        result[i] = 0
for k in range(m):
    print(result[k], end = ' ')

위 코드를 제출하니 시간 초과 라는 결과를 얻게 되었다.

이후, 값이 있는 가 없는 가 탐색하는 알고리즘 중 이진 탐색 알고리즘을 사용하면 이 문제를 풀 수 있음을 알 수 있었다.

이진 탐색 알고리즘

이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 효율적으로 찾는 알고리즘이다.

1. 배열의 중간 요소를 찾는다
2. 중간 요소가 찾고자 하는 값과 같으면 탐색을 종료한다.
3. 중간 요소가 찾고자 하는 값보다 크면, 중간 요소의 왼쪽 부분을 새로운 탐색 범위로 설정한다.
4. 중간 요소가 찾고자 하는 값보다 작으면, 중간 요소의 오른쪽 부분을 새로운 탐색 범위로 설정한다.
5. 새로운 탐색 범위에서 위의 과정을 반복한다.
6. 찾고자 하는 값이 배열 내에 없으면 탐색을 종료한다.

이진 탐색 알고리즘 파이썬 코드 예시

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]

        if guess == target:
            return mid  # 찾은 경우, 인덱스 반환
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1

    return None  # 찾지 못한 경우

# 예시 데이터 
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 5

result = binary_search(arr, target)
if result is not None:
    print(f"{target}은(는) 배열의 {result}번 인덱스에 있습니다.")
else:
    print(f"{target}은(는) 배열에 없습니다.")

이 문제는 탐색 알고리즘을 사용하여 빠르게 값이 있는 지 없는 지 유무를 판단하는 문제이다.