[python/파이썬] 백준 10815 숫자 카드

[문제 출처]

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

10815번: 숫자 카드

 

[소스 코드1 - 시간 초과]

문제를 보자마자 in을 사용하면 되겠구나 쉬운 문제구나 했는데 시간 초과가 났다.

입력이 많기에 in을 사용하여 풀면 시간초과가 나는 문제이다.

import sys
input = sys.stdin.readline

n = int(input()) #상근이 카드 개수
cards = list(map(int, input().split()))

m = int(input()) #정수 개수
number =list(map(int, input().split()))

result = []
for n in number:
  if n in cards:
    result.append(1)
  else:
    result.append(0)


print(*result)

 

[소스 코드2 - 맞았습니다!!]

시간 초과가 나지 않기 위해서는 이진 탐색 방법 혹은 딕셔너리를 사용한 방법으로 풀어야 한다.

이진 탐색이 헷갈렸기에 이진 탐색 코드를 첨부했다.

n = int(input())
cards = list(map(int, input().split()))
m = int(input())
numbers = list(map(int, input().split()))

cards.sort()
for num in numbers:
  low, high = 0, n - 1
  exist = False
  while low <= high:
    mid = (low+high) // 2
    if cards[mid] > num:
      high = mid - 1
    elif cards[mid] < num:
      low = mid + 1
    else:
      exist = True
      break
  print(1 if exist else 0, end = ' ')