[파이썬] 백준 10815 : 숫자 카드 1

[파이썬] 백준 10815 : 숫자 카드 1

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

10815번: 숫자 카드

실버 4

정렬, 이분 탐색

---

코드

import sys
input = sys.stdin.readline


def bs(x, key, ps, pl):
    while True:
        pc = (ps + pl) // 2
        if ps > pl:
            return 0
        elif x[pc] == key:
            return 1
        elif x[pc] < key:
            ps = pc + 1
        elif x[pc] > key:
            pl = pc - 1
    

N = int(input())
cards = sorted(list(map(int, input().split())))
M = int(input())
candidate = list(map(int, input().split()))
ps = 0
pl = len(cards) - 1
for i in range(M):
    print(bs(cards, candidate[i], ps, pl), end = ' ')

굉장히 기본적인 이분 탐색 문제였다. 숫자 카드 2를 풀기 전에 먼저 풀었으면 더 좋았을 것이다.

 

검색해야 할 리스트의 중간 인덱스에 접근하여 찾아야 할 값이 어디 있는지에 따라 검색 범위를 좁혀간다.

단 하나라도 발견되면 바로 반복문을 빠져나와 1을 출력할 수 있도록 하고, 끝까지 찾지 못하면 ps가 pl을 초과하면서 0을 출력하고 반복문을 빠져나오도록 한다.