백준 10815번 풀이

문제

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

10815번: 숫자 카드

숫자 카드 목록에 찾고자 하는 숫자가 있는지 확인하고, 결과를 0 or 1로 출력하는 문제.

 

풀이

일단 이 문제의 입력 인자는 네 개다. 카드 개수, 카드 숫자, 찾을 개수, 찾을 숫자. 그래서 입력을 정직하게 네 줄로 받는다.

 

N = int(sys.stdin.readline())
card_N = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
find_M = list(map(int, sys.stdin.readline().split()))
# 순서대로 카드 장 수/카드/찾을 숫자 개수/찾을 숫자

내가 네 줄 받는다고 했잖아요...

 

그리고 이 문제를 풀기 전에 해야 할 게 두 가지 있다. 첫번째로, 이진 탐색 함수를 정의해야 한다.

def binary_search(target,array):
    left = 0
    right = len(array) - 1

    while left <= right:
        middle = (left + right) // 2
        if array[middle] == target:
            index = middle + 1
            return index
            break
        elif array[middle] > target:
            right = middle - 1
        else: 
            left = middle + 1

이거 정의하면 되고... 아뇨 리턴은 상관 없으니까 걍 정의하시면 됩니다. 그리고 전에 이진 탐색 알고리즘과 정렬 알고리즘에 대해 설명하면서 '정렬 알고리즘을 써서 정렬을 해야 이진 탐색 알고리즘으로 빨리 찾을 수 있다'고 했는데... 이쯤되면 감이 오시겠지만, 리스트 정렬을 해야 한다.

card_N.sort()

그니까 이거. 

 

for i in find_M:
    if binary_search(i,card_N) == None:
        print("0",end=" ")
    else:
        print("1",end=" ")

저 함수를 돌렸을 때 뭔가 있다면 Index를 반환하지만, 찾고자 하는 값이 없으면 None을 반환하게 된다. 즉, 함수 돌려서 None이면 없는거고 다른 뭔가가 나온다면 있는거다. 그래서 이 조건문을 fimd_M(찾을 숫자 배열)만큼 돌리면 된다. 저거는 자바스크립트의 for of와 같은 것으로, 리스트에 직접 접근해서 리스트 요소를 쌩으로 가져온다.