[백준] 10815번 숫자 카드 (Python 파이썬)

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

이 문제는 내가 입력한 숫자들이 상근이가 가지고 있는 숫자들에 존재하는지 확인하는 문제이다.

 

변수 n은 상근이의 숫자 카드 개수, card 는 그 카드들의 숫자 목록이다.

m은 내 카드 개수, check는 내 카드들의 숫자 목록이다.

즉 check의 요소들이 card에 존재 하는가를 검사 하면 된다.

 

이렇게 요소들을 확인하는 문제는 이진탐색(Binary Search) 문제라고 생각하면 쉽다.

요소가 엄청 작은 문제가 아닌 이상, 순차 탐색은 시간초과가 나오기 때문에 이분 탐색을 이용하자.

 

코드는 다음과 같다.

import sys

n = int(input())
card = list(map(int, sys.stdin.readline().split()))
m = int(input())
check = list(map(int, sys.stdin.readline().split()))

card.sort()

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 None


for i in range(m):
    if binary_search(card, check[i], 0, n - 1) is not None:
        print(1, end=' ')
    else:
        print(0, end=' ')

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !