[백준-Python] 좌표 압축 : 18870번

🥈 silver2

 

✅ 1차풀이 : set

import sys
input=sys.stdin.readline

n=int(input())
sangs=set(map(int,input().rstrip().split()))


m=int(input())
num_set=list(map(int,input().rstrip().split()))


for s in num_set:
    # print(s)
    if s in sangs:
        print(1,end=' ')
    else:
        print(0,end=' ')

메모리	실행시간
125620	612

 

중복된 값에 대한 오름차순 정렬 순위를 위해서, set을 사용하였다.

 

 

✅ 2차풀이 : binary Search

import sys
input = sys.stdin.readline

n = int(input())
sangs = list(map(int, input().rstrip().split()))

m = int(input())
num_list = list(map(int, input().rstrip().split()))


sangs.sort()

def binary_search(arr, target):
    start = 0
    end = len(arr) - 1
    
    while start <= end:
        mid = (start + end) // 2
        
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
            
    return False

for target in num_list:
    if binary_search(sangs, target):
        print(1, end=' ')
    else:
        print(0, end=' ')

 

메모리	실행 시간
113328	1868