[백준] 10815번 - 숫자 카드

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

M개의 숫자카드를 순차적으로 돌면서 N개의 숫자카드 안에

속하는지 확인해서 맞으면 1을 아니면 0을 출력하는 문제이다.

 

N가 M의 숫자 카드의 개수는 50만 이하이면서,

숫자 카드의 수는 -1천만~+1천만이기 때문에 순차 탐색은

시간 초과가 걸리게 된다. 그래서 이분 탐색과 같은

빠르게 탐색하는 알고리즘을 사용해야 한다.

 

import sys
input = sys.stdin.readline

n = int(input())
num = list(map(str, input().split()))
num.sort()

m = int(input())
data = list(map(str, input().split()))
result = []

def bisect_search(target, lists):
  start = 0
  end = len(lists) - 1

  while start <= end:
    mid = (start+end) // 2
    if lists[mid] == target: 
      return result.append(1)
    elif lists[mid] < target: start = mid+1
    else: end = mid - 1

  return result.append(0) 

for i in range(len(data)): bisect_search(data[i], num)

print(*result, sep=' ')

 

bisect_search라는 함수를 하나 만들어서

받은 M개의 숫자카드는 target으로,

받은 N개의 숫자카드는 lists로 넣어준다.

 

여기서 주의해야하는 점은 함수 안에 sort()를 수행하면

타겟을 돌 때마다 sort를 하기 때문에 시간초과가 나게 된다.

여기에서는 append를 사용해서 result를 출력했지만,

 

import sys
input = sys.stdin.readline

n = int(input())
num = list(map(str, input().split()))
num.sort()

m = int(input())
data = list(map(str, input().split()))
# result = []

def bisect_search(target, lists):
  start = 0
  end = len(lists) - 1

  while start <= end:
    mid = (start+end) // 2
    if lists[mid] == target: 
      return mid
    elif lists[mid] < target: start = mid+1
    else: end = mid - 1

  return None

for i in range(len(data)):
  if bisect_search(data[i], num) is not None: print(1, end=' ')
  else:  print(0, end=' ')

 

여기에서는 return이 None인가에 따라서 1과 0을 출력하는 방법도

사용할 수 있다. 둘 다 시간은 비슷했다.

이진 탐색의 원리와 코드를 외워두도록 하자.

 

다른 정답 코드들을 보다보니까 기가막힌 코드가 있었다..

 

n,tmp,m = input(),set(input().split()),input()
res = ""
for i in input().split():
    if i in tmp:
        res +="1 "
    else:
        res +="0 "
    print(res)

 

나는 왜 이런 생각을 못했을까,, 하하

 

화이팅 💪💪