[백준] 10815 파이썬(python) : 숫자 카드

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

10815번: 숫자 카드

 

 

n = int(input())
cards = list(map(int, input().split()))
m = int(input())
compare = list(map(int, input().split()))
cards.sort() #1
start, end = 0, n-1 #2
def binary_search(cards, start, end, target): #3
    while start <= end:
        mid = (start + end) // 2
        if cards[mid] == target:
            return mid
        if cards[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return None #4

for com in compare:
    if binary_search(cards, start, end, com) is not None: #5
        print(1, end=" ")
    else:
        print(0, end=" ")

 

#1 : 이분탐색 해야하니까 정렬

#2 : 인덱스는 시작위치는 0, 끝은 입력값의 마지막 인덱스 n-1

#3 : 매개변수로 비교해줄 리스트, 시작, 끝 그리고 target을 넣는다.

#4 : 함수로 이진 탐색을 만들었기 때문에 못찾을 경우에 None을 리턴한다.

#5 : 찾은 경우엔 1을 출력 못찾은 경우엔 0을 출력

 

기본적인 이진탐색 문제인데 못찾을 경우를 어떻게 처리해야 할지를 몰라서 블로그를 찾아봤다. 재귀 형태로 False를 리턴하려하니까 오류 발생하더라 함수형으로 만들어도 while문으로 처리해야 한다는것을 배웠다. 그리고 answer 리스트를 만들고 각각 1과 0을 입력받아서 마지막에 print(*answer)을 하려 했는데 그렇게 하면 append함수를 사용해야해서 시간이 좀 더 걸리는것 같다. 제약사항이 있지 않다면 바로바로 출력하는게 좋을것 같다.