백준 10815 숫자카드 파이썬

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1

1 0 0 1 1 0 0 1

답안 1

• 이진탐색으로 작성

import sys
input = sys.stdin.readline
 
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
 
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None
 
n = int(input())
array_list = list(map(int, input().split()))
array_list.sort()
m = int(input())
target_list = list(map(int,input().split()))
 
 
result_list = []
 
for i in target_list:
    result = binary_search(array_list, i, 0, n - 1)
    if result == None:
        result_list.append(0)
    else:
        result_list.append(1)
print(' '.join(list(map(str,result_list))))

1. 우선 넘어온 리스트를 중간으로 비교한다.
   1. target가 리스트의 중간값의 왼쪽보다 크면 오른쪽으로 탐색하고 오른쪽보다 작으면 왼쪽을 탐색하는 함수를 만든다.
2. 그 다음에 필요한 값들을 받고 비교되는 리스트는 오름차순으로 정렬해서 설정한다.
3. target를 for문을 돌려서 result_list에 담아서 한 번에 출력하면 된다.

답안 2

• 일반적인 target in list 로 작성

import sys
input = sys.stdin.readline
 
N = int(input())
list_one = set(map(int, input().split()))
M = int(input())
list_two = set(map(int,input().split()))
result = []
for i in list_two:
    if i in list_one:
        result.append(1)
    else:
        result.append(0)
print(' '.join(list(map(str,result))))

1. 리스트를 만들때 리스트 대신set을 사용하면 시간초과가 발생하지 않는다.
   1. 집합 연산은 리스트에 비해 순서를 보장하지 않아도 되기 때문에 O(1)에 끝나는 연산들이 더 있다. 따라서 순서를 보장하지 않아도 되는 경우 리스트 대신 집합 타입을 사용해서 시간 복잡도를 줄일 수 있다.
2. 그 다음에 비교할 값을 리스트로 만든다.
3. 비교할 값을 for문을 돌려 비교하면서 리스트에 담아 출력하면 끝이다.