[백준] 10815번: 숫자 카드 (sol.8)

풀이시간: 15분

1. 나의 풀이

# 5분

N = int(input())
have_card = list(map(int, input().split()))

M = int(input())
check_list = list(map(int, input().split()))

ans = []

for ch_num in check_list:
    if ch_num in have_card:
        ans.append('1')
    else:
        ans.append('0')

print(' '.join(ans))

• 시간 초과

# 10분

from bisect import bisect_left, bisect_right

N = int(input())
have_card = sorted(list(map(int, input().split())))

M = int(input())
check_list = list(map(int, input().split()))

ans = []

for ch_num in check_list:
    if abs(bisect_left(have_card, ch_num) - bisect_right(have_card, ch_num)):
        ans.append('1')
    else:
        ans.append('0')

print(' '.join(ans))

• bisect를 사용하여 해당 숫자의 갯수를 찾기
• 없으면 0, 있으면 갯수를 반환

2. 또다른 풀이

N = int(input())
cards = sorted(list(map(int, input().split())))
M = int(input())
qry = list(map(int, input().split()))
ans = []

for q in qry:
	l = bisect_left(cards, q)
    r = bisect_right(cards, q)
    ans.append(1 if r - l else 0)
    
print(*ans)

• left만 써서 해당 자리에 숫자와 일치하는 지 비교하는 것으로도 풀 수 있다.
• 기본 방법은 작성자와 일치

3. 보완할 것

• 파이썬은 초당 2000만번 계산 가능: 최대 입력 갯수보고 최대 계산 갯수를 어림 잡아본다.
• 이분 탐색을 하려면 정렬이 선행되어야 한다.